反 DDoS

题目描述

DDoS 型字符串是指满足以下两个条件的、长度为 $4$、由大写和小写英文字母组成的字符串。

• 第 1、第 2、第 4 个字符为大写英文字母,第 3 个字符为小写英文字母。
• 第 1 个字符和第 2 个字符相同。

例如,DDoS 和 AAaA 是 DDoS 型字符串,而 ddos 和 IPoE 都不是。

给定由大写英文字母、小写英文字母和 ? 组成的字符串 $S$。 设 $q$ 为 $S$ 中 ? 的个数。将 $S$ 中每个 ? 独立地替换为大写或小写英文字母,共可得到 $52^q$ 个字符串。 求其中不以任何 DDoS 型字符串作为子序列的字符串个数,对 $998244353$ 取模。

提示

字符串的子序列是指:从该字符串中删除 0 个或多个字符后,不改变剩余字符的顺序拼接而成的字符串。

例如,AC 是 ABC 的子序列,而 RE 不是 ECR 的子序列。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出答案。

样例

DD??S

676

当两个 ? 中至少有一个被替换为小写英文字母时,得到的字符串都会以 DDoS 型字符串作为子序列。

????????????????????????????????????????

858572093

输出对 $998244353$ 取模后的值。

?D??S

136604

数据范围

• $S$ 由大写英文字母、小写英文字母和 ? 组成。
• $S$ 的长度在 $4$ 到 $3 \times 10^5$ 之间(含端点)。