meow

În clubul de info a apărut un nou pokemon, Meow2. Fiind pasionat de copaci, Meow2 are un arbore cu rădăcină de N noduri, numerotate de la 0 la N - 1. Nodul 0 este rădăcina arborelui și, pentru orice nod diferit de 0, părintele lui are un indice strict mai mic decât el. Fiecare nod i are inițial asociat un număr natural S[i] între 1 și L.

Meow2 ar vrea să știe de câte ori apare șirul 1, 2, ..., L ca subșir “în jos” pe arborele inițial. Formal, e interesat câte șiruri $A_0, A_1, ..., A_{L-1}$ există astfel încât fiecare nod $A_i$ să aibă asociată valoarea i + 1 și, pentru fiecare 0 ≤ i < L - 1 , nodul $A_i$ să fie strămoș (nu neapărat direct) al nodului $A_{i+1}$.

Fiind un pokemon în continuă evoluție, Meow2 schimbă progresiv arborele inițial. Mai exact, acesta are un șir magic de schimbări, P, de lungime Q , la pasul 0 ≤ i < Q schimb ând numărul asociat nodului i % N în P[i], 1 ≤ P[i] ≤ L. Schimbarea de la pasul i va rămâne valabilă și pentru pașii următori.

Meow2 ar vrea să știe după fiecare schimbare de câte ori apare șirul 1, 2, ..., L “în jos” pe arborele inițial. Dacă notăm cu ans[i] răspunsul după a i-a schimbare, trebuie afișată suma: $O = (1 * ans[0] + 2 * ans[1] + … + q * ans[q–1]) \text{ mod } 10^9 + 7$.

Date de intrare

Fișierul de intrare meow.in conține pe prima linie trei numere naturale separate prin câte un spațiu, N, L și Q, cu semnificațiile din enunț.
Următoarea linie conține șirul F de N - 1 numere, numărul F[i] reprezentând tatăl nodului i.
A 3-a linie conține șirul S de lungime N, reprezentând valorile inițiale ale nodurilor din arbore.
Apoi urmează Q linii ce formează șirul P, reprezentând schimbările pe care le face Meow2 asupra arborelui în modul prezentat în enunț, în ordine.

Date de ieșire

Fișierul meow.out va conține suma O cerută modulo $10^9+7$.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ L ≤ N
• 0 ≤ F[i] < i, pentru orice i
• 1 ≤ P[i], S[i] ≤ L, pentru orice i
• 1 ≤ Q ≤ 200 000
• Pentru 20 de puncte: N ≤ 200, L ≤ 30, Q ≤ 400
• Pentru 50 de puncte: N ≤ 5 000, L ≤ 300, Q ≤ 5 000

Exemple

meow.in

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

meow.out

29

Explicație

În arborele inițial, șirul S apare de 3 ori, dar după prima operație va apărea de 0 ori, după a doua operație tot de 0 ori, după a treia operație o dată, după a patra operație o dată, după a cincea operație de 2 ori, dupa a sașea operație de 2 ori.
Răspunsul este 1 * 0 + 2 * 0 + 3 * 1 + 4 * 1 + 5 * 2 + 6 * 2 = 29