#P14488. [2025年广东省队集训]小方的疑惑

    ID: 13707 传统题 1500ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600树形DP组合数学动态规划拓扑排序

[2025年广东省队集训]小方的疑惑

问题描述

小方(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

数据范围

对于所有数据,保证 0≤ai≤1090\le a_i\le 10^9。

测试点编号 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。