Problem Statement

Let's call a string T of length 3N, containing exactly N letters A, N letters B, and N letters C, good, if it can be split into N (not necessarily contiguous) subsequences of length 3, so that the letters from each subsequence form ABC, BCA, or CAB.
You are given a string S of length 3N, consisting of characters A, B, C, and ?.
Count the number of ways to replace each ? with one of A, B, and C, so that the resulting string is good. As this number can be very large, output it modulo 998244353.

Input

Input is given from Standard Input in the following format:
N
S

Output

Print the answer modulo 998244353.

Constraints

• $1\le N \le 15$.
• S is a string of length 3N, consisting of A, B, C, and ?.

Sample Input 1

1
???

Sample Output 1

3

There are 3 good strings you can obtain: ABC, BCA, and CAB.

Sample Input 2

2
AA????

Sample Output 2

2

There are 2 good strings you can obtain: AABBCC and AABCBC.

Sample Input 3

3
?A?A?A?A?

Sample Output 3

0

It's impossible to obtain a good string, as there are already 4 A's.

Sample Input 4

9
?????????A??B??C???????????

Sample Output 4

331653164

见题面 Input 部分

见题面 Output 部分