#P2022B. Subsequence

    ID: 113 Type: Default 1000ms 256MiB Tried: 9 Accepted: 6 Difficulty: 9 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Subsequence

Subsequence

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

We define the "JIE number" of a string TT is the number of triples (i,j,k)(i,j,k) that satisfy all the following conditions:

1.1i<j<kT1\leq i < j < k \leq |T|(T|T| is the length of TT).

2.Ti=J,Tj=I,Tk=ET_i = 'J', T_j = 'I', T_k = 'E'.

Frank is given a string SS that contains only 3 characters: J,I,E'J','I','E'. However, due to hacker's attack, some characters of SS are replaced with ?'?'.If QQ is the number of the occurrences of ?'?' in SS, we can make 3Q3^Q strings by replacing each occurrence of '?' in S with J'J',I'I',E'E'.

Frank is now wonder the sum of JIE numbers of all the 3Q3^Q strings. This is easy for him so he ask you to solve it.

Since the answer may be very large, you only need to tell him the result modulo 998244353998244353.

Input

The input contains only one string S(3S105)S(3\leq|S|\leq10^5). It is guaranteed that each character in SS is 'J','I','E' or '?'.

Output

Print a single integer, denoting the answer to the question modulo 998244353998244353.

J??E
8

Notes

The 3Q3^Q strings are: JJJE,JJIE,JJEE,JIJE,JIIE,JIEE,JEJE,JEIE,JEEEJJJE,JJIE,JJEE,JIJE,JIIE,JIEE,JEJE,JEIE,JEEE, and their contribution to the answer are: 0+2+0+1+2+2+0+1+0=80+2+0+1+2+2+0+1+0 = 8.