#P17242. [2025年南开中学集训]小方的疑惑

[2025年南开中学集训]小方的疑惑

(square)

小方(275307894a\color{black}2\color{red}75307894a)是一名国家集训队队员,他一直有很多疑惑。

这天,小 L 送给他了一个长度为 nn 的正整数序列 aa 和一个长度为 n−1n-1 的正整数序列 bb(下标均从 11 开始),其中序列 bb 满足 1≤bi≤i1\le b_i\le i。

小方可以执行如下操作若干次:

  • 选择一个 i(1≤i<n)i(1\le i<n) 满足 abi>0a_{b_i}>0,将 abia_{b_i} 减去 11,将 ai+1a_{i+1} 增加 11。

小方很疑惑有多少种本质不同的序列 aa 可以被生成,可他想了很久却想不到一个优秀的做法,请你帮帮他。

由于答案很大,所以要对 109+710^9+7 取模。

输入格式

第一行一个正整数 nn。

第二行 n−1n-1 个正整数 b1,b2,⋯ ,bn−1b_1,b_2,\cdots,b_{n-1}。

第三行 nn 个非负整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。

输出格式

一行一个数,表示最终的答案。

输入输出样例

样例输入 1
4
1 1 2
1 1 1 0
样例输出 1
7
样例 1 解释

可以被生成的序列 aa 的为:[1,1,1,0][1,1,1,0],[1,0,1,1][1,0,1,1],[0,1,2,0][0,1,2,0],[0,0,2,1][0,0,2,1],[0,2,1,0][0,2,1,0],[0,1,1,1][0,1,1,1],[0,0,1,2][0,0,1,2]。

样例输入 2
6
1 1 2 2 3
1 1 4 5 1 4
样例输出 2
63
样例输入/输出 3~7

详见下发文件 ex_square3~7.in/ex_square3~7.out。

数据范围

对于所有数据,保证 0≤ai≤109,1≤bi≤i0\le a_i\le 10^9,1\le b_i\le i。

测试点编号 n=n= 特殊性质
11 55 A
2,32,3 无
4,54,5 100100
6,76,7 500500 A
8∼108\sim 10 无
11∼1311\sim 13 8×1038\times 10^3 A
14∼1614\sim 16 B
17∼2517\sim 25 无

特殊性质 A:对于任意 1≤i≤n1\le i\le n 均满足 ai=1a_i=1。

特殊性质 B:对于任意 2≤i≤n2\le i\le n 均满足 bi=⌊i+12⌋b_i=\lfloor\frac {i+1}2\rfloor。