munte

O permutare de ordin $N$ se numeste $permutare-munte$ daca si numai daca pentru fiecare $i$, $1 \leq i \leq N$, $i$ par, conditia $v[i-1]>v[i]<v[i+1]$ are loc. Daca $i=N$, doar conditia $v[i-1]>v[i]$ trebuie sa aiba loc.

De exemplu permutarea de ordin 5 $[2, 1, 4, 3, 5]$ este o $permutare-munte$, deoarece $2>1<4$ si $4>3<5$, dar permutarea de ordin 5 $[2, 1, 5, 4, 3]$ nu este o $permutare-munte$ deoarece $5>4>3$, deci pentru $i=4$ conditia nu este indeplinita.

O permutare de ordin $N$ este un sir de $N$ elemente care contine toate elementele de la $1$ pana la $N$ in orice ordine. De exemplu, sirul $[1, 4, 5, 2, 3]$ este o permutare de ordin $5$, dar sirurile $[1, 3, 2, 3, 5]$ si $[1, 2, 3, 5, 6]$ nu sunt permutari de ordin $5$.

Se dă un număr $N$. Să se afle numarul permutărilor-munte de ordinul $i$, $1 \leq i \leq N$. Deoarece raspunsul poate fi foarte mare, cerem doar restul impartirii raspunsului la un alt numar dat, $M$.

Date de intrare

Pe prima linie se va afla numarul naturale $N$, reprezentand numarul de ordin cu care trebuie sa faceti permutarile, si $M$, restul la care trebuie sa aflati raspunsul.

Date de ieșire

Pe prima linie se va afisa rezultatul modulo $M$.

Restricții și precizări

• $1 \leq N \leq 5000$
• $1 \leq M \leq 10^9$
• $M$ este prim
• $M > N$

Exemplu

stdin

5 19

stdout

6

Explicatie

Numarul permutarilor-munte cu ordinul $\leq 5$ este $25$. $2$ dintre aceste permutari sunt $[4, 1, 3, 2]$ si $[3, 1, 2]$.