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

Poveste şi cerinţă...

Să considerăm un şir de cifre $c$, si să fie $S(c)$ mulţimea subşirurilor nevide ale lui $c$ (de exemplu, dacă $c = 123$ atunci $S(c) = {1, 2, 3, 12, 13, 23, 123}$). Fie hipervaloarea $h(c)$ a lui $c$ suma elementelor lui $S(c)$, considerate ca numere in baza $10$ (de exemplu, $h(c) = 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 b x$, prin care $c[a], c[a+1], ..., c[b]$ iau 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.

h2. Date de intrare

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

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.

h2. Date de ieşire

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

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

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