← 返回题目列表

AtCoder · agc055_d

D. ABC 最后通牒

中文机器翻译题面 查看原题

分数: 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