Etichetare

Cerință

Miki a terminat de pregătit murăturile pentru iarnă și acum dorește să eticheteze cele $N$ borcane pe care le-a umplut. El are la dispoziție $K$ etichete, numerotate de la $1$ la $K$.

Procesul de etichetare al borcanelor se va desfășura în următorul fel:

• Initial Miki alege un borcan cu indicele $idx_1$ ($1 \leq idx_i \leq N$), și îi aplică eticheta cu numărul $1$ $(e_{idx_1}=1)$;
• Pentru fiecare etichetă următoare, de la $2$ la $K$, Miki selectează un nou borcan, cu indicele $idx_i$ ($1 \leq idx_i \leq N$), astfel încât diferența dintre indicii borcanelor consecutive să fie exact $1$ $(\lvert idx_i−idx_{i−1}\rvert =1)$. Borcanul selectat va primi eticheta cu numărul corespunzător;
• Dacă un borcan selectat are deja o etichetă, Miki va înlocui eticheta existentă cu cea nouă.

Prietenul său, Denis, i-a propus o etichetare finală a borcanelor$^1$ - $e_1, e_2, \ldots,e_N$. Acum, Miki se întreabă în câte moduri distincte ar putea obține etichetarea propusă, respectând procesul de etichetare menționat mai sus$^2$. Ajutați-l pe Miki să calculeze acest număr modulo $998\ 244\ 353$.

Date de intrare

Pe prima linie, se vor afla două numere întregi $N$ și $K$ - numărul de borcane, respectiv numărul de etichete.

Pe a doua linie se vor afla $N$ numere $e_1, e_2, \ldots, e_N$ - etichetarea propusă de Denis.

Date de ieșire

Se va afișa o singură linie ce conține un singur număr întreg - numărul de modalități distincte prin care Miki poate obține etichetarea propusă de Denis modulo $998\ 244\ 353$.

Restricții și precizări

• $^1$În cazul în care un borcan cu indicele $i$ rămâne neetichetat, eticheta acestuia va fi $e_i=0$;
• $^2$Un proces de etichetare este considerat diferit de alt proces dacă ordinea borcanelor etichetate este diferită;
• $2 \leq N \leq 5\ 000$;
• $1 \leq K \leq 10\ 000$;
• $0 \leq e_i \leq K$;
• Dacă $i \neq j$, $e_i \neq 0$ și $e_j \neq 0$, atunci $e_i \neq e_j$;
• Se garantează că etichetarea propusă de Denis este validă.

Subtask-uri

Exemplul 1

stdin

4 9
1 8 9 6

stdout

2

Explicație

Pentru primul exemplu există două procese de etichetare distincte:

• $1\ 2\ 3\ 4\ 3\ 4\ 3\ 2\ 3$;
• $1\ 2\ 3\ 2\ 3\ 4\ 3\ 2\ 3$.

Exemplul 2

stdin

6 16
0 5 16 15 12 11

stdout

18