Fişierul intrare/ieşire:	hipersir.in, hipersir.out	Sursă	Science On 2021, clasele 11-12
Autor	Tamio-Vesa Nakajima	Adăugată de	Mihaela Cismaru •MihaelaCismaru
Timp execuţie pe test	0.75 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

Date de ieşire

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

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.

Exemplu

Cum se trimit solutii?