Meow

meow

== include(page="template/taskheader" task_id="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 ]) mod 10^9^ + 7$.
 

Poveste şi cerinţă...

h2. 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.

Fişierul de intrare $meow.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $meow.out$ ...

h2. Restricţii

* $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$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. meow.in |_. meow.out |

|6 2 6
0 1 0 3 0
1 2 1 2 1 2
2
1
2
1
2
1
|29

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. 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$

...

== include(page="template/taskfooter" task_id="meow") ==