reversez

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 $Suffix_S[i]$ = sufixul stringului $S$ care începe la poziția $i$. Având stringul $S$, o să creăm șirul $A[i] = lcp(S, Suffix_S[i])$.

Cerință

Cunoscând șirul $A$ și lungimea alfabetului $\Sigma$, să determine câte stringuri $S$ generează sirul $A$.

Date de intrare

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 a doua se vor afla $N$ numere naturale reprezentând șirul $A$.

Date de ieșire

Î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$.

Restricții si precizări

• $ 1 \leq N \leq 300 000$
• $ 1 \leq Sigma \leq 100 000$
• Numărul de soluții va fi cel puțin $1$.

Exemplu

reversez.in

4 3
4 1 0 1

reversez.out

6 

Explicație

Dacă $\Sigma$ = $\set{1,2,3}$, cele $6$ stringuri $S$ posibile sunt:

• 1121
• 1131
• 2212
• 2232
• 3313
• 3323