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^$

* $1 ≤ T ≤ 10$;
* $1 ≤ N ≤ 10^100^$;
* 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.

h2. Exemplu
table(example). |_. oltenesc.in |_. oltenesc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
33
999
232323
992391662939123897
| 32
938
194003
515744048

|
h3. 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ă).

== include(page="template/taskfooter" task_id="oltenesc") ==