meow

Meow

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

Poveste şi cerinţă...

Î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 $S$ “î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$.
 

h2. Date de intrare