It's game night at Amplitude, which means a group of individuals are playing The Gang!

Actually, this summer, The Gang is not as popular. That doesn't stop there from being a problem that is tangentially related.

Nick came up with the following problem idea themed around The Gang and expected values: you are given a string ~s~ that only contains four characters: A, G, N, and ?. Nick will independently and uniformly at random take each question mark and replace it with one of A, G or N. Compute the expected number of times GANG appears as a subsequence in the string.

Expected values are terrifying to people at Amplitude, so he has modified the problem slightly. Instead of computing the expected value, consider all possible strings that can be obtained after independently replacing each question mark with one of A, G, or N. For each such string, count the number of times GANG appears as a subsequence, and sum these counts over all possible strings.

Because the number of ways that GANG can appear as a subsequence can be very large, please keep track of the number of ways modulo ~998244353~. It is highly recommended that you maintain a running count of the answer modulo ~998244353~ and not simply output the final result modulo ~998244353~.

The number of times GANG appears as a subsequence in a string ~s~ is equal to the number of unique ~4~-tuples ~(a, b, c, d)~ where ~a < b < c < d~, ~s_a = G~, ~s_b = A~, ~s_c = N~, and ~s_d = G~.

Constraints

~1 \le |s| \le 10^5~

Subtask 1 [1 point]

~|s| \le 8~

Subtask 2 [1 point]

~|s| \le 30~

Subtask 3 [1 point]

No additional constraints.

Input Specification

The first and only line of input contains a single string ~s~. It is guaranteed each character in ~s~ comes from AGN?.

Output Specification

Let ~S~ be the sum of the total number of times GANG appears a subsequence over all strings that can be obtained from ~s~.

Output the remainder when ~S~ is divided by 998244353.

Sample Input 1

????

Sample Output 1

1

Sample Explanation 1

There is exactly one string that has GANG appear as a subsequence - namely, GANG.

This test case will be the first test case in the first subtask.

Sample Input 2

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

Sample Output 2

799755681

Sample Explanation 2

It can be shown that the total number of ways that GANG can appear as a subsequence is ~3794488740~. ~3794488740~ when divided by ~998244353~ leaves a remainder of ~799755681~.

This test case will be the first test case in the second subtask.