== include(page="template/taskheader" task_id="kmax") ==

Aurorei îi plac mult permutările. Ea defineşte o kmax-permutare ca fiind o permutare cu următoarea proprietate: pentru orice subsecvenţă cu elementele în ordine crescătoare, lungimea subsecvenţei este cel mult egală cu $K$. Acum, Aurora se întreabă câte kmax-permutări cu $N$ elemente există.

Aurorei îi plac mult permutările. Ea defineşte o $kmax-permutare$ ca fiind o permutare cu următoarea proprietate: pentru orice subsecvenţă cu elementele în ordine crescătoare, lungimea subsecvenţei este cel mult egală cu $K$. Acum, Aurora se întreabă câte $kmax-permutări$ cu $N$ elemente există.

h2. Cerinta

h2. Cerinţă

Pentru valorile $N, K şi R$ date, aflaţi numărul de kmax-permutări cu $N$ elemente. Rezultatul va fi calculat **modulo $R$**.

Pentru valorile $N, K şi R$ date, aflaţi numărul de $kmax-permutări$ cu $N$ elemente. Rezultatul va fi calculat **modulo $R$**.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire kmax.out va conţine o singură linie pe care veţi scrie numărul de kmax-permutări cu $N$ elemente, **modulo R**.

Fişierul de ieşire $kmax.out$ va conţine o singură linie pe care veţi scrie numărul de $kmax-permutări$ cu $N$ elemente, **modulo R**.

h2. Restricţii

* $1 ≤ K ≤ N ≤ 300$
* $10 ≤ R ≤ 30000$

* $1 ≤ K ≤ N ≤ 300$
* $10 ≤ R ≤ 30000$

* O subsecvenţă a unei permutări este formată din elemente situate pe poziţii consecutive.

* Pentru $20%$ din teste $N ≤ 10$
* Pentru $60%$ din teste $N ≤ 150$

* Pentru $20%$ din teste $N ≤ 10$
* Pentru $60%$ din teste $N ≤ 150$

h2. Exemplu

| 21690
|

h2. Explicatie

h3. Explicatie

Dintre cele $24$ de permutări de $4$ elemente NU sunt 2max-permutări următoarele $7$:

Dintre cele $24$ de permutări de $4$ elemente NU sunt $2max-permutări$ următoarele $7$:

$1 2 3 4$
$1 2 4 3$
$1 3 4 2$

4775