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 $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])$.

Cerință

Cunoscând șirul $A$ și lungimea alfabetului $\Sigma$, să determine câte stringuri $S$ generează șirul $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 $2$ 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 $666 \ 013$.

Restricții și 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={1,2,3}$, cele $6$ stringuri $S$ posibile sunt:
1121, 1131, 2212, 2232, 3313, 3323