$0982$
$2453$

Din când în când Anastasia schimbă câte o cifră de pe tablă (îi distruge opera artistică a Zoei

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!
 
h2. Date de intrare
 
Pe prima linie din fişierul de intrare $adunare2.in$ 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$.
 
h2. Date de ieşire
 
În fişierul de ieşire $adunare2.out$ 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$.
 
h2. Restricţii
 
* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$
* Pentru $20$ de puncte, $N ≤ 20$, $Q = 0$.
* Pentru alte $30$ de puncte, $N ≤ 1.000, Q ≤ 1.000$.
 
h2. Exemplu
 
table(example). |_. adunare2.in |_. adunare2.out |
|4 1
1531
0982
2453
1 1 2
| 4
4|
 
==Include(page="template/taskfooter" task_id="adunare2")==