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 ≤ 30010 ≤ R ≤ 30000- O subsecvenţă a unei permutări este formată din elemente situate pe poziţii consecutive.
- Pentru
20%din testeN ≤ 10 - Pentru
60%din testeN ≤ 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