序列中正整数的众数（majority element）是指出现次数至少占该序列元素总数一半的数。

如果一个序列的所有非空连续子段都至少包含一个众数，则称该序列为“好”序列。例如，$[1, 2, 1, 1, 3]$ 是好序列，因为其子段如 $[1, 1, 3]$、$[1, 2]$ 和 $[2, 1, 1, 3]$ 都包含众数；但 $[1, 2, 1, 3]$ 不是好序列，因为 $[2, 1, 3]$ 不包含众数。

给定一个由 $1, 2, 3$ 和 $?$ 组成的字符串，请计算将每个 $?$ 替换为 $1, 2, 3$ 中的一个，使得最终序列成为好序列的方案数。输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 200$)，表示字符串的长度。 第二行包含一个长度为 $N$ 的字符串，由 $1, 2, 3$ 和 $?$ 组成。

输出格式

输出答案对 $10^9 + 7$ 取模后的余数。

子任务

• (10 分) $N \le 10$，输入仅包含 $?$。
• (20 分) $N \le 25$，输入仅包含 $?$。
• (40 分) $N \le 60$。
• (30 分) 无附加限制。

样例

样例输入 1

3
???

样例输出 1

21

样例输入 2

3
12?

样例输出 2

2

样例输入 3

4
1?11

样例输出 3

3

样例输入 4

5
12213

样例输出 4

0

样例输入 5

10
???1??????

样例输出 5

1735

说明

对于第一个样例，在 $3^3 = 27$ 种可能的数组中，不是好序列的只有 $[1, 2, 3]$ 及其全排列，因此答案为 $27 - 3! = 21$。

对于第二个样例，$[1, 2, 1]$ 和 $[1, 2, 2]$ 是好序列，但 $[1, 2, 3]$ 不是。

对于第三个样例，$[1, 1, 1, 1]$、$[1, 2, 1, 1]$ 和 $[1, 3, 1, 1]$ 均为好序列。

对于第四个样例，由于 $[1, 2, 2, 1, 3]$ 不是好序列，因此答案为零。