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

Să considerăm un şir de cifre $s$, si să fie $S(s)$ mulţimea subşirurilor nevide ale lui $s$ (de exemplu, dacă $s = 123$ atunci $S(s) = {1, 2, 3, 12, 13, 23, 123}$). Fie hipervaloarea $h(s)$ a lui $s$ suma elementelor lui $S(s)$, considerate ca numere in baza $10$ (de exemplu, $h(123) = 1 + 2 + 3 + 12 + 13 + 23 + 123 = 177$).
 
Se dă un şir de cifre $c[1] ... c[N]$, şi $Q$ operaţii de două tipuri:
 
* $1 a x$, prin care $c[a]$ ia valoarea $x$.
* $2 a b$, prin care se cere $h(c[a], c[a+1], ..., c[b]) % 1.000.000.007$.
 
Să se efectueze toate aceste operaţii.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $hipersir.in$ conţine, pe prima linie de input, numerele $N$, $Q$.
Pe a doua linie se găseşte şirul de cifre $c$.
Pe următoarele $Q$ linii se găsesc operaţiile efectuate.

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

h2. Date de ieşire

În fişierul de ieşire $hipersir.out$ se vor afişa rezultatele operaţiilor, pe linii diferite.

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

h2. Restricţii

* $1 ≤ N ≤ 300.000$
* $1 ≤ Q ≤ 300.000$
* Pentru 20 de puncte $1 ≤ N ≤ 15, 1 ≤ Q ≤ 100$.
* Pentur alte 20 de puncte $1 ≤ N ≤ 1.000, 1 ≤ Q ≤ 1.000$.

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

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

| 3 4
000
1 1 1
1 2 2
1 3 3
2 1 3
| 177
|
| 10 10
1373429614
1 7 1
2 7 8
1 8 8
1 3 0
1 5 3
1 2 8
2 1 9
2 5 8
1 1 2
1 3 8
|23
530826057
4585

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

|

h3. Explicaţie
 
...
 

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