分数: 1200 点
问题陈述
让我们调用一个字符串 T 长度 3N,恰好包含 N 字母 A, N 字母 B,和 N 字母 C, 好,如果可以拆分为 N (不一定连续)长度子序列 3,使得每个子序列中的字母形成 ABC, BCA,或 CAB.
给你一个字符串 S 长度 3N,由字符组成 A, B, C,和 ?。
计算每种替换方式的数量 ? 与其中之一 A, B,和 C,这样生成的字符串就很好。由于这个数字可能非常大,因此输出它的模 998244353.
约束
- 1\le N \le 15.
- S 是一个长度为 3N,包括
A,B,C,和?.
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案模数 998244353.
示例输入 1
1 ???
示例输出 1
3
有 3 你可以获得的好字符串: ABC, BCA,和 CAB.
示例输入 2
2 AA????
示例输出 2
2
有 2 你可以获得的好字符串: AABBCC 和 AABCBC.
示例输入 3
3 ?A?A?A?A?
示例输出 3
0
不可能获得好的字符串,因为已经有 4 A的。
示例输入 4
9 ?????????A??B??C???????????
示例输出 4
331653164