hacker

Hacker

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

Poveste si cerinta...

Nargy vrea sa afle parola de la mail-ul lui Fumeanu ca sa ii faca o farsa. Dupa mai multe cercetari Nargy a aflat ca parola lui Fumeanu este un numar de $N$ cifre in baza $K$ care are urmatoarea proprietate: orice prefix de lungime $i < N$ al numarului este diferit de sufixul corespunzator de lungime $i$. Mai mult de atat, Nargy stie si ce cifre se afla pe anumite pozitii din parola.
Nefiind un hacker prea priceput singura metoda de a sparge o parola pe care o stie Nargy este 'brute force':http://en.wikipedia.org/wiki/Brute_force_attack. Astfel, el ar vrea sa stie inainte cate posibilitati exista pentru parola lui Fumeanu folosind informatiile pe care le are pana acum.

h2. Date de intrare

Fisierul de intrare $hacker.in$ ...

Fisierul de intrare $hacker.in$ contine pe prima linie numerele $N$ si $K$. Urmatoarea linie contine $N$ caractere care pot fi numere intre $0$ si $K-1$ sau caracterul $?$ pentru pozitiile din parola care nu se cunosc.

h2. Date de iesire

In fisierul de iesire $hacker.out$ ...

In fisierul de iesire $hacker.out$ se va afisa numarul de posiblitati pentru parola lui Fumeanu, modulo $666013$.

h2. Restrictii

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

* $1 ≤ N ≤ 2.000$
* $2 ≤ K ≤ 10$

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

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

| 4 2
| 1??0 | 3 |

h3. Explicatie

...

Cele $3$ parole posibile:
* $1000$
* $1100$
* $1110$
$1010$ nu este o parola valida deoarece prefixul de lungime $2$ ($10$) este egal cu sufixul de lungime $2$ ($10$).

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