题目描述

A, B, C をそれぞれちょうど $N$ 個ずつ含む長さ $3N$ の文字列 $T$ が次の条件を満たすとき、$T$ を良い文字列と呼びます: $T$ を $N$ 個の長さ $3$ の（連続とは限らない）部分列に分解する方法であって、各部分列が ABC, BCA, CAB のいずれかであるような方法が存在する。

A, B, C, ? からなる長さ $3N$ の文字列 $S$ が与えられます。各 ? を A, B, C のいずれかに置き換える方法であって、結果が良い文字列となるようなものの個数を求めてください。この個数は非常に大きい可能性があるため、これを $998244353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

答えを $998244353$ で割った余りを出力せよ。

题目大意

称一个长度为 $3n$，只由 $\text{A,B,C}$ 组成的字符串是好的，当且仅当其能划分成 $n$ 个长度为 $3$ 的子序列，每个子序列都是 $\text{ABC}$，或者 $\text{BCA}$，或者 $\text{CAB}$。求把问号替换成 $\text{A,B,C}$ 使得字符串是好的的方案数 $\bmod\ 998244353$。

1
???

3

2
AA????

2

3
?A?A?A?A?

0

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

331653164

提示

制約

• $1\le\ N\ \le\ 15$
• $S$ は、A, B, C, ? からなる長さ $3N$ の文字列である。

Sample Explanation 1

得られる良い文字列は、ABC, BCA, CAB の $3$ 個です。

Sample Explanation 2

得られる良い文字列は、AABBCC, AABCBC の $2$ 個です。

Sample Explanation 3

A が既に $4$ 個含まれるため、良い文字列を得ることはできません。