AT_agc055_d [AGC055D] ABC Ultimatum

当且仅当一个长度为 $3N$ 的字符串 $T$，恰好包含 $N$ 个 `A`、$N$ 个 `B` 和 $N$ 个 `C`，并且存在一种将 $T$ 分解为 $N$ 个长度为 $3$ 的（不一定连续的）子序列的方法，使得每个子序列都是 `ABC`、`BCA` 或 `CAB` 之一时，我们称 $T$ 为**好字符串**。 现给定一个由 `A`、`B`、`C`、`?` 组成的长度为 $3N$ 的字符串 $S$。请你计算有多少种将每个 `?` 替换为 `A`、`B` 或 `C` 的方案，使得最终得到的字符串是好字符串。由于答案可能非常大，请输出答案对 $998244353$ 取模的结果。

输入从标准输入中给出，格式如下： > $N$ $S$

输出一个整数，表示方案数对 $998244353$ 取模的结果。

### 限制条件 - $1 \leq N \leq 15$ - $S$ 是一个由 `A`、`B`、`C`、`?` 组成的长度为 $3N$ 的字符串。 ### 样例解释 1 可以得到的好字符串有 `ABC`、`BCA`、`CAB` 共 $3$ 个。 ### 样例解释 2 可以得到的好字符串有 `AABBCC`、`AABCBC` 共 $2$ 个。 ### 样例解释 3 由于已经包含 $4$ 个 `A`，无法得到好字符串。 由 ChatGPT 4.1 翻译