Aurorei îi plac mult permutările. Ea defineşte o kmax-permutare ca fiind o permutare pentru care orice subsecvenţă a ei ce are elementele în ordine crescătoare, are lungime mai mică sau egală decât k. Acum, Aurora se întreabă câte kmax-permutări cu N elemente există.
Cerinţă
Pentru un N, k şi R daţi, 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 printr-un spaţiu.
Date de ieşire
Pe prima şi singura linie a fişierului de ieşire kmax.out veţi afişa numărul de kmax-permutări cu N elemente, modulo R.
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
Exemple
kmax.in
kmax.out
Explicaţii
4 2 997
17
Dintre cele 24 de permutări de 4 elemente următoarele 7 NU sunt 2max-permutări:
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ă câte observaţi toate cele 7 permutări de mai sus au cel puţin o secvenţă cu elementele în ordine crescătoare de lungime mai mare decât 2.