题目背景

很久很久以前，小 A 在一棵无穷深的三叉树上摘苹果，这棵苹果树的根没有苹果，每个点三个儿子的苹果的数量分别是这个点的苹果数量的三倍加上 $0,1,2$，小 A 从根节点一直往下走了正好 $d$ 步并摘到了 $k$ 个苹果，可惜的是，小 A 只记得 $k$ 在三进制下的某些位，他想知道有多少种方式符合他的记忆。

题目描述

有一棵深度无穷大的以 $0$ 为根的三叉树，节点 $i$ 的儿子分别是节点 $3i+1,3i+2,3i+3$。

设节点 $i$ 的点权为 $a_i$。对于 $0\le j\le 2$，有 $a_{3i+j+1}=3\times a_i+j$，特别的，$a_0=0$。

你的任务是求从根出发，找长度 $=d$ 的简单路径，并使得该路径经过的所有点的点权和为 $k$。你需要求出所有合法路径的条数。

然而 $k$ 并不唯一，$k$ 的三进制表示中仅有某些位是已知的，而其它的位将以字符 $\tt ?$ 表示。你需要对所有可能的 $k$ 在上述问题中的答案求和，最后再对 $10^9+7$ 取模。

输入格式

第一行一个整数 $d$。

第二行一个长度为 $d$ 的字符串，表示三进制形式的 $k$。注意 $k$ 可能有前导零。

输出格式

输出一行一个整数，表示你所求的答案。

3
?12

3

3
???

19

4
0211

1

10
21??1?2??0

161

30
???1????0????1???0????2???????

744432249

提示

样例 #1 解释

合法的路径有：

• $[0,1,5,17]$
• $[0,2,7,23]$
• $[0,2,9,30]$

对应的点权分别为：

• $[0,0,1,4]$
• $[0,1,3,10]$
• $[0,1,5,17]$

数据范围

测试点编号	$d$	特殊性质
$1\sim 2$	$\leq15$	-
$3$	$\leq50$	A
$4$		B
$5\sim 8$		-
$9\sim 10$	$\leq300$	A
$11\sim 12$		B
$13\sim 14$		-
$15$	$\leq2000$	A
$16$		B
$17\sim 20$		-

特殊性质 A：保证 $k$ 中 $?$ 的数量 $\leq 1$。

特殊性质 B：保证所有的位置均为 $?$。

对于 $100\%$ 的数据，$1\le d\le 2000,0\le k\lt 3^{d+1}$。