Meow

In the CS club there's a new Pokemon, Meow2. Being passionate about trees, Meow2 has a rooted tree with $N$ nodes, labeled from $0$ to $N-1$. Node $0$ is the root of the tree, and every for every other node $i$ its father has a label smaller than $i$. Each node has an associated value, an integer between $1$ and $L$.

Meow2 also has an array $S=[1,2,\dots ,L]$ of length $L$. He wants to know the number of occurrences of $S$ in the tree. More exactly, he wants to count the number of sequences $A_1,A_2,\dots ,A_L$​ such that the value associated with node $A_i=i$, and for each $1≤i<L$ node $A_i$ is an ancestor of node $A_{i+1}$.

Being an ever evolving Pokemon, Meow2 keeps changing the initial tree. He has a magical array of changes, $P$, of length $Q$. At each step $i$, $0≤i<Q$, he changes the value of node $i\%N$ to $P_i$, $1≤P_i≤L$.

Meow2 would like to know after each change the number of occurrences of $S$ in the tree, as defined above. If we denote by $ans_i$ the number of occurrences of $S$ after the $i$th change, you should find:

• $O=1 \times ans_0+2 \times ans_i+\dots +Q \times ans_{Q-1}$

The first line contains $3$ integers $N$, $L$ and $Q$.

The second line contains an array $F$ of length $N-1$, where $F_i$ is the father of node $i$.

The third line contains an array of length $N$, representing the initial values of the nodes.

The next $Q$ lines contains an integer each, representing the changes made on the tree.

Output a single integer $O$ modulo $10^9+7$.

• $1≤N≤10^5$
• $1≤L≤N$
• $1≤Q≤2 \times 10^5$

The individual answers are: $0,0,1,1,2,2$

Below you can see the tree after the first update