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ă.

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.

Date de intrare

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.

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.

Restricţii şi precizări

• 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

Exemplu

kmax.in

4 2 997		

kmax.out

17

Explicaţie

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.

kmax.in

30 10 27017	

kmax.out

21690