Adunare

Anastasia și Zoe se joacă pe tabla din sala de clasă. Zoe scrie trei rânduri de cifre pe tablă:
$1531 \\ 0982 \\ 2453 \\$

Din când în când Anastasia schimbă câte o cifră de pe tablă (îi distruge opera artistică a Zoei ☺). După fiecare modificare de genul acesta (și înainte de toate modificările), Anastasia o întreabă pe Zoe: în câte moduri ai putea șterge coloane astfel încât valoarea din primul rând, adunată cu valoarea din al doilea rând, să fie egală cu valoarea din al treilea rând? De exemplu, putem șterge primele trei coloane (care ne dă $1 + 2 = 3$), a treia coloană ($151 + 92 = 243$), a treia și ultima coloană ($15 + 9 = 24$), sau toate coloanele ($0 + 0 = 0$), deci răspunsul ar fi $4$.

Ajutați-o pe Zoe să răspundă la întrebările Anastasiei!

Date de intrare

Pe prima linie din fișierul de intrare se vor găsi valorile $N$ și $Q$: numărul de cifre scrise de Zoe pe fiecare rând inițial, respectiv numărul de modificări și întrebări făcute de Anastasia.

Urmează trei linii, fiecare cu câte $N$ cifre zecimale, neseparate prin spații. După acestea veți găsi câte $Q$ linii. O linie conține numerele $i, j, c :$ Anastasia modifică cifra de pe rândul $i$ și coloana $j$ în $c$.

Date de ieșire

în fișierul de ieșire se vor afișa $Q + 1$ numere, fiecare pe câte un rând. Primul număr va reprezenta răspunsul la întrebarea Anastasiei, modulo $1 \ 000 \ 000 \ 007$, înainte de toate modificările, iar numerele ce urmează reprezintă răspunsurile după fiecare modificare, tot modulo $1 \ 000 \ 000 \ 007$.

Restricții

• $1 ≤ N ≤ 100 \ 000$
• $1 ≤ Q ≤ 100 \ 000$

Subtask 1 (20 puncte)

• $N ≤ 20$
• $Q = 0$

Subtask 2 (30 puncte)

• $N ≤ 1 \ 000$
• $Q ≤ 1 \ 000$

Subtask (50 puncte)

• Fară restricții suplimentare.

Exemplu

stdin

4 1
1531
0982
2453
1 1 2

stdout

4
4