#P12607. 三叉求和

三叉求和

题目背景

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

题目描述

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

设节点 ii 的点权为 aia_i。对于 0j20\le j\le 2,有 a3i+j+1=3×ai+ja_{3i+j+1}=3\times a_i+j,特别的,a0=0a_0=0

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

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

输入格式

第一行一个整数 dd

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

输出格式

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

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,1,5,17]
  • [0,2,7,23][0,2,7,23]
  • [0,2,9,30][0,2,9,30]

对应的点权分别为:

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

数据范围

测试点编号 dd 特殊性质
121\sim 2 15\leq15 -
33 50\leq50 A
44 B
585\sim 8 -
9109\sim 10 300\leq300 A
111211\sim 12 B
131413\sim 14 -
1515 2000\leq2000 A
1616 B
172017\sim 20 -

特殊性质 A:保证 kk?? 的数量 1\leq 1

特殊性质 B:保证所有的位置均为 ??

对于 100%100\% 的数据,1d2000,0k<3d+11\le d\le 2000,0\le k\lt 3^{d+1}