oltenesc

Oltenesc

== include(page="template/taskheader" task_id="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 $10^9^ + 7$.

!>{width:14%}problema/oltenesc?amza.png!
 
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 $10^9^ + 7$.

h2. Cerinţă

h2. 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.

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.

h2. Restricţii
* $1 ≤ T ≤ 10$;
* $1 ≤ N ≤ 10^100^$;

* Pentru $10$% din teste avem că $N ≤ 10^6^$.

* Pentru $10$% din teste avem că $T = 1$ şi $N ≤ 10^6^$.

* Pentru $50$% din teste avem că $N ≤ 10^18^$.
* 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.