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

Cerință

Se dă un şir de cifre $c_1, c_2, \dots, 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}, \dots, c_b)$ modulo $1 \ 000 \ 000 \ 007$.

Să se efectueze toate aceste operaţii.

Date de intrare

Fişierul de intrare hipersir.in conţine, pe prima linie de input, numerele $N$ si $Q$.

Pe a doua linie se găseşte şirul de cifre $c$.

Pe următoarele $Q$ linii se găsesc operaţiile efectuate.

Date de ieșire

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

Restricții și precizări

• $1 \leq N \leq 300 \ 000$
• $1 \leq Q \leq 300 \ 000$
• Pentru teste in valoare de $20$ de puncte: $1 \leq N \leq 15$, $1 \leq Q \leq 100$.
• Pentru alte teste in valoare de $20$ de puncte: $1 \leq N \leq 1 \ 000$, $1 \leq Q \leq 1 \ 000$.

Exemplul 1

hipersir.in

3 4
000
1 1 1
1 2 2
1 3 3
2 1 3

hipersir.out

177

Exemplul 2

hipersir.in

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

hipersir.out

23
530826057
4585