#P13070. [AGC055D] ABC Ultimatum

    ID: 12254 传统题 2000ms 888MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-线性 DP计数 DP状态维度消除滚动数组

[AGC055D] ABC Ultimatum

题目描述

当且仅当一个长度为 3N3N 的字符串 TT,恰好包含 NN 个 A、NN 个 B 和 NN 个 C,并且存在一种将 TT 分解为 NN 个长度为 33 的(不一定连续的)子序列的方法,使得每个子序列都是 ABC、BCA 或 CAB 之一时,我们称 TT 为好字符串。

现给定一个由 A、B、C、? 组成的长度为 3N3N 的字符串 SS。请你计算有多少种将每个 ? 替换为 A、B 或 C 的方案,使得最终得到的字符串是好字符串。由于答案可能非常大,请输出答案对 998244353998244353 取模的结果。

输入格式

输入从标准输入中给出,格式如下:

NN SS

输出格式

输出一个整数,表示方案数对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

1
???

输出 #1

3

输入输出样例 #2

输入 #2

2
AA????

输出 #2

2

输入输出样例 #3

输入 #3

3
?A?A?A?A?

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

331653164

说明/提示

限制条件

  • 1≤N≤151 \leq N \leq 15
  • SS 是一个由 A、B、C、? 组成的长度为 3N3N 的字符串。

样例解释 1

可以得到的好字符串有 ABC、BCA、CAB 共 33 个。

样例解释 2

可以得到的好字符串有 AABBCC、AABCBC 共 22 个。

样例解释 3

由于已经包含 44 个 A,无法得到好字符串。