reversez

Reversez

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

Poveste şi cerinţă...

Considerăm un alfabet cu $Sigma$ caractere. Notam $lcp(S, P)$ = cel mai lung prefix comun dintre un string $S$ şi un string $P$. Pentru un string $S$ o să notăm $SuffixS[i]$ = sufixul stringului $S$ care începe la poziţia $i$. Având stringul $S$, o să creăm şirul $A[i] = lcp(S, SuffixS[i])$.
 
h2. Cerinta
 
Cunoscând şirul $A$ şi lungimea alfabetului $Sigma$, să determine câte stringuri $S$ generează sirul $A$.

h2. Date de intrare

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

Pe prima linie a fişierului de intrare *reversez.in* se vor afla doua numere naturale $N$ şi $Sigma$, cu semnificaţia din enunţ.
Pe linia 2 se vor afla $N$ numere naturale reprezentând şirul $A$.

h2. Date de ieşire

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

În fişierul de ieşire *reversez.out* veţi afişa un singur număr natural reprezentând numărul de stringuri $S$ cerut, $modulo 666013$.

h2. Restricţii

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

* $1 ≤ N ≤ 300 000$
* $1 ≤ Sigma ≤ 100 000$
* Numărul de soluţii va fi cel puţin 1.

h2. Exemplu

table(example). |_. reversez.in |_. reversez.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. reversez.in |_. reversez.out |_. Explicatie |
| 4 3
4 1 0 1
| 6
| Dacă Sigma={1,2,3}, cele 6 stringuri S posibile sunt:
1121
1131
2212
2232
3313
3323
|

...

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