cifrul

Por Costel si Cifrul

== include(page="template/taskheader" task_id="cifrul") ==

Poveste şi cerinţă...

Por Costel a gasit legendarul seif despre care se spune ca “ascunde atata mancare incat un om se poate hrani o viata intreaga”. El crede ca ii va ajunge pentru micul dejun, insa trebuie mai intai sa treaca de mecanismul ei defensiv care seamana foarte mult (in mod curios) cu cel al unei valize.
Pentru a deschide seiful, el trebuie sa introduca un cod de lungime <tex>N</tex> (<tex>N</tex> cifre de la de la <tex>0</tex> la <tex>K-1</tex>). Codul se introduce prin intermediul a <tex>N</tex> rotite. Acestea pot fi actionate in sus sau in jos (daca o rotita indica valoarea <tex>x</tex>, ea poate fi actionata printr-o singura miscare sa indice valoarea <tex>(x+1)</tex> <tex>mod</tex> <tex>K</tex> sau sa indice valoarea <tex>(x-1)</tex> <tex>mod</tex> <tex>K</tex>).
Legenda spune ca seiful a fost faurit de <tex>M</tex> porci stravechi. De aceea, exista <tex>M</tex> coduri distincte care pot deschide seiful. Mai mult, seiful s-a deteriorat cu timpul iar acum fiecare rotita din cele <tex>N</tex> are o “marja de eroare” data printr-un numar <tex>D</tex>. Ce inseamna acest lucru este ca un cod <tex>X</tex> va deschide seiful daca exista un cod din cele <tex>M</tex> pentru care: <tex>distanta(X_i,M_i)</tex> &le; <tex>D</tex> oricare <tex>i</tex> de la <tex>1</tex> la <tex>N</tex> unde:
 
* distanta dintre doua cifre <tex>a</tex> si <tex>b</tex> insemna numarul minim de actionari ale unei rotite pentru a trece de la cifra <tex>a</tex> la cifra <tex>b</tex>
* <tex>X_i</tex> insemna a <tex>i</tex>-a cifra din codul <tex>X</tex>, analog definim <tex>M_i</tex>
 
Cum sistemul a fost proiectat de niste porci, era de asteptat sa nu fie de prea mare calitate. Exista foarte multe combinatii care deschid seiful, atat de multe incat noi va cerem sa calculati numarul lor modulo <tex>10^9 + 7</tex>. Por Costel deja se linge pe bot de pofta !
 

h2. Date de intrare

Fişierul de intrare $cifrul.in$ ...

Fişierul de intrare $cifrul.in$ va contine pe prima linie <tex>T</tex>, numarul de teste, pe urmatoarele linii vor fi descrise testele astfel: prima linie va contine <tex>N</tex>, <tex>M</tex>, <tex>K</tex>, <tex>D</tex>, urmatoarele <tex>M</tex> linii contin cate <tex>N</tex> numere separate prin spatii (reprezentand codurile celor M porci stravechi). A <tex>i</tex>-a dintre aceste linii descrie al <tex>i</tex>-lea cod

h2. Date de ieşire

În fişierul de ieşire $cifrul.out$ ...

În fişierul de ieşire $cifrul.out$ va contine <tex>T</tex> linii, fiecare avand numarul cerul pentru testul respectiv.

h2. Restricţii

* $... ≤ ... ≤ ...$

* <tex>1</tex> &le; <tex>T</tex> &le; <tex>6</tex>
* <tex>1</tex> &le; <tex>N</tex> &le; <tex>100</tex>
* <tex>1</tex> &le; <tex>M</tex> &le; <tex>12</tex>
* <tex>1</tex> &le; <tex>K,D</tex> &le; <tex>10^6</tex>

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

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

| 2
1 2 10000 3
1
6
3 1 100 5
1 6 30
| 12
1331

|

h3. Explicaţie
 
...
 

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

10328