树（tree）

题目描述

给定一棵有根树，共有 $N$ 个节点，节点编号为 $0,1,\ldots,N-1$，根节点为 $0$。

对于每个 $i=0,1,\ldots,N-2$，节点 $i+1$ 的父亲为 $F[i]$。保证：

$$0\le F[i]\le i$$

因此，每个节点的父亲编号都小于它本身的编号。

每个节点 $u$ 有一个点权 $A[u]$，满足：

$$1\le A[u]\le L$$

定义一条长度为 $L$ 的节点序列 $B[1],B[2],\ldots,B[L]$ 是一条合法序列，当且仅当同时满足：

1. 对于所有 $i=1,2,\ldots,L$，有：

   $$A[B[i]]=i$$

2. 对于所有 $i=2,3,\ldots,L$，节点 $B[i]$ 是节点 $B[i-1]$ 的祖先。

也就是说，序列中点权依次为 $1,2,\ldots,L$，并且后一个节点必须是前一个节点的祖先。

现在会进行 $Q$ 次修改。第 $i$ 次修改，其中 $0\le i<Q$，会把节点：

$$i\bmod N$$

的点权修改为 $P[i]$。

令 $ans_i$ 表示第 $i$ 次修改完成后，当前树上合法序列的数量。

你不需要输出每一次的 $ans_i$，只需要计算：

$$O=\sum_{i=0}^{Q-1}(i+1)\times ans_i \pmod {10^9+7}$$

你的任务是实现指定函数，返回 $O$。

---

提交方式

本题为提交函数题。

你需要提交一个源文件，实现如下函数：

int calc(int N, int L, int Q,
         std::vector<int> F,
         std::vector<int> A,
         std::vector<int> P);

评测程序会负责读入数据并调用你的 calc 函数。

你提交的代码中：

• 不应包含 main 函数；
• 不需要自行读入；
• 不需要自行输出；
• 只需要返回答案 $O$。

---

参数说明

• N：树的节点数。
• L：合法序列的长度，也是点权的取值范围。
• Q：修改次数。
• F：长度为 $N-1$ 的数组，其中 F[i] 表示节点 $i+1$ 的父亲。
• A：长度为 $N$ 的数组，其中 A[i] 表示节点 $i$ 的初始点权。
• P：长度为 $Q$ 的数组，其中 P[i] 表示第 $i$ 次修改后的新点权。
• 函数需要返回整数 $O$。

---

样例

调用：

calc(6, 2, 6,
     {0, 1, 0, 3, 0},
     {1, 2, 1, 2, 1, 2},
     {2, 1, 2, 1, 2, 1});

在这个样例中：

ans = [0, 0, 1, 1, 2, 2]

因此：

$$O=1\times 0+2\times 0+3\times 1+4\times 1+5\times 2+6\times 2=29$$

所以函数应返回：

29

---

数据范围与限制

对于所有测试数据，满足：

• $1\le N\le 10^6$
• $1\le L\le N$
• $1\le Q\le 2\times 10^6$
• $0\le F[i]\le i$
• $1\le A[i]\le L$
• $1\le P[i]\le L$

---

子任务

1. $10$ 分：$N\le 200$，$L\le 30$，$Q\le 400$。
2. $20$ 分：$N\le 5000$，$L\le 300$，$Q\le 5000$。
3. $20$ 分：对于所有 $i$，均有 $F[i]=i$。
4. $30$ 分：$N\le 10^5$，$Q\le 2\times 10^5$。
5. $20$ 分：无特殊限制。

---

样例评测程序说明

样例评测程序会按照如下格式读入数据：

N L Q
F[0] F[1] ... F[N-2]
A[0] A[1] ... A[N-1]
P[0] P[1] ... P[Q-1]

然后调用：

calc(N, L, Q, F, A, P)

并输出该函数的返回值。

输出格式为：

O