kmax

Kmax

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

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $kmax.in$ ...

Pe prima linie a fişierului de intrare $kmax.in$ se vor afla numerele naturale $N, K şi R$, având semnificaţiile din enunţ, separate între ele prin câte un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $kmax.out$ ...

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$
* 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$

h2. Exemplu
table(example). |_. kmax.in |_. kmax.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2 997
| 17

|

 
h3. Explicaţie
 
...

| 30 10 27017
| 21690
|
 
h3. Explicatie
 
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$
$2 1 3 4$
$2 3 4 1$
$3 1 2 4$
$4 1 2 3$
După cum se observă, toate cele şapte permutări de mai sus au cel puţin o secvenţă cu elementele în ordine crescătoare de lungime mai mare decât $2$.

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

4775