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