Državno natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 3. zadatak - Dan 2

Ana: Znaš li što je palindrom?

Milovan: Ne znam, je li to nešto kao aerodrom?

Ana: Ne, to je niz znakova koji se jednako čita slijeva nadesno kao i zdesna nalijevo. Na primjer: “kisik”, “121”, “00100”, “sirimamiris”, itd...

Milovan: Dobro.

Ana: Zanima li te kako određujem ljepotu brojeva?

Milovan: Pa...

Ana: Ljepota broja jednaka je broju načina da se zapis tog broja rastavi na dijelove tako da svaki dio bude palindrom. Na primjer, ljepota broja 10010 iznosi 4. Jedan mogući rastav na palindrome je 1|0|010 (okomite crte predstavljaju granice između dijelova). Ostala tri načina su: 1|0|0|1|0, 1|00|1|0 i 1001|0.

Milovan: A brojevi 121 i 789?

Ana: Broj 121 može se rastaviti na dva načina (1|2|1 i 121), a broj 789 na samo jedan način (7|8|9).

Milovan: Zanimljivo... Evo ti onda jedan zadatak: nađi mi zbroj ljepote svih prirodnih brojeva između A i B, uključivo.

Ana: Samo tren... Evo, traženi zbroj je X!

Milovan: Impresivno!

ULAZNI PODACI

U prvom i drugom retku nalaze se redom dva prirodna broja A i B (1 ≤ A ≤ B ≤ 10^3000).

IZLAZNI PODACI

Ispišite ostatak pri dijeljenju broja X s brojem 10^9 + 7, pod pretpostavkom da je Anin račun točan.

PRIMJERI TEST PODATAKA

ulaz

100
101

izlaz

4

ulaz

5069
133506

izlaz

248868

ulaz

3001004001005009001331
4011312005608897002034

izlaz

61887243