题目描述

英大文字・英小文字からなる長さ $4$ の文字列で、以下の $2$ 条件をともに満たすものを DDoS 型文字列と呼ぶことにします。

• $1,2,4$ 文字目が英大文字で、$3$ 文字目が英小文字である
• $1,2$ 文字目が等しい

例えば DDoS, AAaA は DDoS 型文字列であり、ddos, IPoE は DDoS 型文字列ではありません。

英大文字・英小文字および ? からなる文字列 $S$ が与えられます。 $S$ に含まれる ? を独立に英大文字・英小文字に置き換えてできる文字列は、$S$ に含まれる ? の個数を $q$ として $52^q$ 通りあります。 このうち DDoS 型文字列を部分列に含まないものの個数を $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

答えを出力せよ。

题目大意

• 定义形如 DDoS 的序列为类 DDoS 序列，其中 DD 表示两个相同的任意大写字母，o 表示任意小写字母，S 表示任意大写字母。
• 给定一个由大小写字母和 ? 组成的序列 $S$，问有多少种将 ? 替换为大小写字母的方案可以使 $S$ 不含有任何一个类 DDoS 子序列，答案对 $998244353$ 取模。
• $4 \le \left|S\right| \le 3 \times 10^5$

DD??S

676

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

858572093

?D??S

136604

提示

注記

文字列の部分列とは、文字列から $0$ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことをいいます。
例えば、AC は ABC の部分列であり、RE は ECR の部分列ではありません。

制約

• $S$ は英大文字・英小文字および ? からなる
• $S$ の長さは $4$ 以上 $3\times\ 10^5$ 以下

Sample Explanation 1

? の少なくとも一方が英小文字のとき、DDoS 型文字列を部分列に含みます。

Sample Explanation 2

$998244353$ で割ったあまりを求めてください。