Hacker

hacker

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

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.

Poveste si cerinta...

h2. Date de intrare

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.

Fisierul de intrare $hacker.in$ ...

h2. Date de iesire

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

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

h2. Restrictii

* $1 ≤ N ≤ 200$
* $2 ≤ K ≤ 10$
* Numarul poate incepe cu cifra $0$

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

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

| 4 2
 1??0 | 3 |

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

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") ==

2492