/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
A, B, C をそれぞれちょうど N 個ずつ含む長さ 3N の文字列 T が次の条件を満たすとき、T を良い文字列と呼びます: T を N 個の長さ 3 の（連続とは限らない）部分列に分解する方法であって、各部分列が ABC, BCA, CAB のいずれかであるような方法が存在する。
A, B, C, ? からなる長さ 3N の文字列 S が与えられます。各 ? を A, B, C のいずれかに置き換える方法であって、結果が良い文字列となるようなものの個数を求めてください。この個数は非常に大きい可能性があるため、これを 998244353 で割った余りを出力してください。
制約
- 1\le N \le 15
- S は、
A,B,C,?からなる長さ 3N の文字列である。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
1 ???
出力例 1
3
得られる良い文字列は、ABC, BCA, CAB の 3 個です。
入力例 2
2 AA????
出力例 2
2
得られる良い文字列は、AABBCC, AABCBC の 2 個です。
入力例 3
3 ?A?A?A?A?
出力例 3
0
A が既に 4 個含まれるため、良い文字列を得ることはできません。
入力例 4
9 ?????????A??B??C???????????
出力例 4
331653164
Score : 1200 points
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.
Constraints
- 1\le N \le 15.
- S is a string of length 3N, consisting of
A,B,C, and?.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the answer modulo 998244353.
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