F - Anti-DDoS Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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

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

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

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

注記

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

制約

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

入力

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

S

出力

答えを出力せよ。

入力例 1

DD??S

出力例 1

676

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

入力例 2

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

出力例 2

858572093

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

入力例 3

?D??S

出力例 3

136604

Score : 500 points

Problem Statement

A DDoS-type string is a string of length 4 consisting of uppercase and lowercase English letters satisfying both of the following conditions.

  • The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
  • The first and second characters are equal.

For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.

You are given a string S consisting of uppercase and lowercase English letters and ?. Let q be the number of occurrences of ? in S. There are 52^q strings that can be obtained by independently replacing each ? in S with an uppercase or lowercase English letter. Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo 998244353.

Notes

A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.

Constraints

  • S consists of uppercase English letters, lowercase English letters, and ?.
  • The length of S is between 4 and 3\times 10^5, inclusive.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

DD??S

Sample Output 1

676

When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.

Sample Input 2

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

Sample Output 2

858572093

Find the count modulo 998244353.

Sample Input 3

?D??S

Sample Output 3

136604