AT_agc055_d [AGC055D] ABC Ultimatum

[problemUrl]: https://atcoder.jp/contests/agc055/tasks/agc055_d `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 $ で割った余りを出力せよ。

### 制約 - $ 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 $ 個含まれるため、良い文字列を得ることはできません。