题目描述

假设一个长度为 $3N$ 的字符串 $T$，其中恰好包含 $N$ 个字母 A，$N$ 个字母 B 和 $N$ 个字母 C。如果可以将字符串拆分为 $N$ 个长度为 $3$ 的子序列（不一定连续），使得每个子序列中的字母构成 ABC、BCA 或 CAB，则称该字符串 good。

给定一个长度为 $3N$ 的字符串 $S$，由字符 A、B、C 和 ? 构成。计算替换其中的每个 ? 为 A、B 和 C 中的一个字符，使得得到的字符串是 good 的方式数。由于结果可能非常大，输出结果对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 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