O permutare p a mulţimii {1, 2, 3, …, n} (permutare de ordin n) îndeplineşte condiţia H dacă p(i)<p(i/2) pentru orice i, 1<i≤n.
Cerinţă
Calculaţi numărul de permutări de ordin n care îndeplinesc condiţia H, modulo M (M număr prim).
Date de intrare
Pe prima linie a fişierului de intrare hperm.in sunt scrise numerele n şi M, separate de un spatiu.
Date de ieşire
Fişierul de ieşire hperm.out va conţine o singură linie pe care va fi scris restul împărţirii la M a numărului permutărilor de ordin n care îndeplinesc condiţia H.
Restricţii
2 ≤ n ≤ 10000
M număr natural prim din intervalul [2, 32000].
Pentru 50% din teste M<1000
Exemple
hperm.in
hperm.out
Explicaţii
5 13
8
Cele 8 permutări de ordin 5 care au proprietatea H sunt: 5 3 4 1 2
5 3 4 2 1
5 4 3 1 2
5 4 3 2 1
5 4 1 3 2
5 4 1 2 3
5 4 2 1 3
5 4 2 3 1