题目描述

信息学俱乐部里出现了一只新的宝可梦 Meow2。Meow2 喜欢树，因此它有一棵带根树，共有 $N$ 个节点，编号为 $0$ 到 $N-1$。

节点 $0$ 是根。对于任意非根节点，它的父亲节点编号都严格小于它。每个节点 $i$ 初始有一个自然数标签 $S_i$，满足 $1\le S_i\le L$。

Meow2 想知道，在这棵初始树上，序列

$$1,2,\ldots,L$$

作为“向下子序列”出现了多少次。

形式化地说，它关心有多少个节点序列

$$A_0,A_1,\ldots,A_{L-1}$$

满足：

• 节点 $A_i$ 的标签为 $i+1$；
• 对每个 $0\le i<L-1$，节点 $A_i$ 是节点 $A_{i+1}$ 的祖先，祖先不要求是直接父亲。

Meow2 正在不断进化，因此它会逐步修改树上节点的标签。它有一个长度为 $Q$ 的魔法修改序列 $P$。在第 $i$ 次修改，$0\le i<Q$，它会把节点

$$i\bmod N$$

的标签改为 $P_i$，其中 $1\le P_i\le L$。一次修改会对之后的所有步骤继续生效。

Meow2 想知道，每次修改之后，序列 $1,2,\ldots,L$ 作为“向下子序列”出现了多少次。设第 $i$ 次修改后的答案为 $ans_i$，其中 $0\le i<Q$。你需要输出：

$$O=\left(1\cdot ans_0+2\cdot ans_1+\cdots+Q\cdot ans_{Q-1}\right)\bmod (10^9+7).$$

输入格式

第一行包含三个自然数 $N,L,Q$，含义如题所述。

第二行包含 $N-1$ 个整数，记为 $F_1,F_2,\ldots,F_{N-1}$，其中 $F_i$ 表示节点 $i$ 的父亲。

第三行包含长度为 $N$ 的序列 $S$，表示各节点的初始标签。

接下来 $Q$ 行，每行一个整数，依次构成修改序列 $P$。第 $i$ 行修改会把节点 $i\bmod N$ 的标签改为对应的 $P_i$。

输出格式

包含一个整数，表示题目要求的 $O$，对 $10^9+7$ 取模。

数据范围与约定

• $1\le N\le 100000$；
• $1\le L\le N$；
• 对任意 $i$，$0\le F_i<i$；
• 对任意 $i$，$1\le P_i,S_i\le L$；
• $1\le Q\le 200000$。

子任务：

分值	限制
20	$N\le 200,\ L\le 30,\ Q\le 400$
50	$N\le 5000,\ L\le 300,\ Q\le 5000$
100	原始限制

样例

输入

6 2 6
0 1 0 3 0
1 2 1 2 1 2
2
1
2
1
2
1

输出

29

解释

在初始树中，序列 $1,2$ 出现 $3$ 次。

但是在各次修改之后，答案依次为：

$$0,0,1,1,2,2.$$

所以最终输出：

$$1\cdot0+2\cdot0+3\cdot1+4\cdot1+5\cdot2+6\cdot2=29.$$