P12607 三叉求和

很久很久以前，小 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$ 可能有前导零。

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

### 样例 #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$|$\leq50$|B| |$5\sim 8$|$\leq50$|-| |$9\sim 10$|$\leq300$|A| |$11\sim 12$|$\leq300$|B| |$13\sim 14$|$\leq300$|-| |$15$|$\leq2000$|A| |$16$|$\leq2000$|B| |$17\sim 20$|$\leq2000$|-| 特殊性质 A：保证 $k$ 中 $?$ 的数量 $\leq 1$。 特殊性质 B：保证所有的位置均为 $?$。 对于 $100\%$ 的数据，$1\le d\le 2000,0\le k\lt 3^{d+1}$。