| Fişierul intrare/ieşire: | oltenesc.in, oltenesc.out | Sursă | Empowersoft 2019 |
| Autor | Andrei Constantinescu | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Oltenesc
Un număr X se numeşte oltenesc dacă nu conţine nici o putere de 2 de cel puţin 2 cifre ca subsecvenţă în scrierea sa zecimala. Nea Mărin are un număr N format din cel mult 100 de cifre şi se întreabă câte numere naturale cel mult egale cu N sunt olteneşti. Deoarece răspunsul poate fi destul de mare, se cere doar restul împărţirii sale la 109 + 7.
Cerinţă
Se dau T întrebări, fiecare constând dintr-un singur număr N. Pentru fiecare întrebare să se calculeze câte numere 0 ≤ X ≤ N sunt olteneşti, modulo 109 + 7.
Date de intrare
Pe prima linie a fişierului oltenesc.in se află numărul T. Urmează T linii, fiecare conţinând câte un număr N format din cel mult 100 de cifre zecimale, reprezentând o întrebare.
Date de ieşire
Fişierul de ieşire oltenesc.out va conţine T linii, constând în răspunsurile la cele T întrebări din fişierul de intrare.
Restricţii
- 1 ≤ T ≤ 10;
- 1 ≤ N ≤ 10100;
- Pentru 10% din teste avem că T = 1 şi N ≤ 106.
- Pentru 50% din teste avem că N ≤ 1018.
- Prin subsecvenţă a unui număr zecimal înţelegem numărul obţinut prin păstrarea unei secvenţe continue formate din cifrele numărului iniţial. De exemplu, 234, 12 şi 12345 sunt subsecvenţe ale numărului 12345, dar 135 şi 432 nu sunt.
Exemplu
| oltenesc.in | oltenesc.out |
|---|---|
| 4 33 999 232323 992391662939123897 | 32 938 194003 515744048 |
Explicaţie
Singurele numere care nu sunt olteneşti cuprinse intre 0 şi 33 sunt 16 şi 32. Singurele numere care nu sunt olteneşti cuprinse intre 0 şi 999 sunt 128, 256, 512 şi cele de formele 16?, 32?, 64?, ?16, ?32, ?64 (observaţi cum numărul 164 se regăseşte de 2 ori în această listă).
