Revenge of UMG

H: Revenge of UMG

problem

For the character string T consisting of three types of characters,'U',' M', and'G', the 1, 2, ..., | T | characters are T_1, T_2, ..., T_ {|, respectively. When we decide to express T |}, we call the number of pairs of (i, j, k) that satisfy the following conditions the "UMG number" of the string T:

• 1 \ leq i <j <k \ leq | T |
• j --i = k --j
• T_i ='U', T_j ='M', T_k ='G'

Now, we are given the string S, which consists of the four characters'U',' M',' G', and'?'. There are 3 ^ {N} possible strings that can be created by replacing the'?' In S with one of'U',' M', or'G', respectively, where N is the number of'?'. Find the sum of the UMG numbers in the string divided by 998244353.

Input format

S

Constraint

• 3 \ leq | S | \ leq 2 \ times 10 ^ {5}
• S is a character string consisting of four types of characters,'U',' M',' G', and'?'.

Output format

Print the integer that represents the answer on one line. Note that it prints too much divided by 998244353.

Input example 1

? MG?

Output example 1

3

If the first'?' Is not a'U', the UMG number will be 0. When the first'?' Is'U'

• The number of UMGs in UMGU is 1
• The number of UMGs in UMGM is 1
• The number of UMGs in UMGG is 1

And the total value is 3.

Input example 2

UUMMGGGUMG

Output example 2

Four

Input example 3

????? G ???? U ??? M ?????? G ????? M ???? G ??? U ?????? M ??? G ??

Output example 3

648330088

Please answer too much divided by 998244353.

Example

Input

?MG?

Output

3

inputFormat

Input format

S

Constraint

• 3 \ leq | S | \ leq 2 \ times 10 ^ {5}
• S is a character string consisting of four types of characters,'U',' M',' G', and'?'.

outputFormat

Output format

Print the integer that represents the answer on one line. Note that it prints too much divided by 998244353.

Input example 1

? MG?

Output example 1

3

If the first'?' Is not a'U', the UMG number will be 0. When the first'?' Is'U'

• The number of UMGs in UMGU is 1
• The number of UMGs in UMGM is 1
• The number of UMGs in UMGG is 1

And the total value is 3.

Input example 2

UUMMGGGUMG

Output example 2

Four

Input example 3

????? G ???? U ??? M ?????? G ????? M ???? G ??? U ?????? M ??? G ??

Output example 3

648330088

Please answer too much divided by 998244353.

Example

Input

?MG?

Output

3

样例

?MG?

3