3. O Žabovej krutovláde

Kde bolo tam bolo, žil raz jeden krutý vládca, ktorý sa volal Žaba. Ľuďom sa pod jeho nadvládou žilo ťažko. Od východu slnka až po jeho západ museli všetci tvrdo pracovať na jeho poliach, dbať o vyváženosť stromov v jeho záhrade, starať sa o čistotu na jeho hrade¹, plniť všetky príkazy, ktoré mu napadli, … A to všetko bez nároku na nejakú odmenu.

Spod Žabovej nadvlády sa dalo dostať iba tak, že ste si získali jeho rešpekt. A to sa oficiálne robilo tak, že Žaba vám dal programátorskú úlohu a dve hodiny času. Ak ste ju vyriešili v časovom limite, boli ste voľní, a mohli ste emigrovať do susednej krajiny. Ak nie, tak vás Žaba nechal slávnostne popraviť.

Erik sa rozhodol vyskúšať svoje štastie. Žaba mu zadal nasledujúcu úlohu: “Na vstupe dostaneš reťazec pozostávajúci z cifier \(0\) až \(9\). Tvojou úlohou je vypočítať, aké číslo by sme dostali, ak by sme sčítali všetky jeho súvislé podreťazce, modulo \(10^9 + 7\).”

Erik si s úlohou nevie rady. Naštastie, v dnešnej modernej dobe majú ľudia schopnosť telepatie². Pomôžte mu!

Úloha

Súvislým podreťazcom daného reťazca \(s\) v tejto úlohe nazývame ľubovoľný neprázdny reťazec, ktorý vznikne odstránením niekoľkých (nula alebo viac) znakov zo začiatku a niekoľkých znakov z konca reťazca \(s\). Dva súvislé podreťazce reťazca \(s\) považujeme za rôzne, ak sa líšia v počte znakov, ktoré sme pri ich vytvorení odstránili zo začiatku, alebo z konca reťazca \(s\) (aj keby inak vyzerali úplne rovnako). Napríklad reťazec baca má \(10\) súvislých podreťazcov: b, a, c, a, ba, ac, ca, bac, aca, baca (všimnite si, že reťazec a rátame dvakrát).

Na vstupe dostanete reťazec znakov, ktorý obsahuje len cifry \(0, 1, \ldots, 9\). Znaky sa môžu ľubovoľne opakovať a reťazec môže začínať aj ľubovoľným počtom núl. Vašou úlohou je vypočítať súčet všetkých jeho súvislých podreťazcov. Výsledok môže byť veľmi veľké číslo, vypíšte preto jeho zvyšok po delení \(10^9 + 7\).

Formát vstupu

Na jedinom riadku vstupu je reťazec \(s\), ktorý obsahuje aspoň \(1\) a najviac \(10^6\) znakov z rozsahu 0 až 9.

Formát výstupu

Vypíšte jedno číslo: súčet všetkých súvislých podreťazcov, modulo \(10^9 + 7\).

Príklad

Input:

123

Output:

164

\(1 + 2 + 3 + 12 + 23 + 123 = 164\)

Input:

001

Output:

3

Input:

4369383968

Output:

353343059

Input:

447723168365033648256648424988

Output:

42233771