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

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