Pracsiu Dan (dnprx) Azi este ziua secvenței! Profesoara de mate a scris câteva secvențe pe tablă, fiecare având N numere distincte cuprinse între 1 și N, și le-a spus studenților că aceste secvențe au o proprietate specială. După o analiză atentă, Deni, una din studente, a ghicit corect proprietatea. Toate secvențele de pe tablă au cel puțin o pereche de numere adiacente de forma (x, x+1). Deni a fost așa de fericită încât a denumit acest tip de secvențe drăguțe. De exemplu, pentru N = 4 secvențele 3,1,2,4 și 2,3,4,1 sunt drăguțe, dar secvențele 2,4,1,3 și 4,3,2,1 nu sunt. După aceea, profesoara de mate i-a dat lui Deni o problemă mai dificilă. I s-a cerut să calculeze numărul de secvențe drăguțe formate din N numere distincte cuprinse între 1 și N. Această problemă a fost așa de grea încât Deni nu a putut afla răspunsul pe durata orei de clasă. Tu ești prieten cu Deni și vrei să o ajuți.
Cerința
Scrieți programul care pentru un N dat trebuie să-i spună lui Deni care este numărul de secvențe drăguțe. Acest număr poate fi foarte mare, așa că trebuie calculat modulo M.
Date de intrare
De pe prima linie a intrării standard se citesc două numere întregi N și M – lungimea secvențelor de pe tablă și numărul modulo folosit pentru calcul.
Date de ieșire
Pe o linie din ieșirea standard, programul trebuie să afișeze un singur întreg, numărul de secvențe drăguțe formate din N numere distincte de la 1 la N, modulo M.
Restricții și precizări
1 ≤ N ≤ 10181 ≤ M ≤ 107
Subtaskuri
- Subtask 1 (0 puncte) : Exemplele
- Subtask 2 (9 puncte) :
N ≤ 10 - Subtask 3 (14 puncte) :
N ≤ 15 - Subtask 4 (11 puncte) :
N ≤ 20 - Subtask 5 (43 puncte) :
N ≤ 1.000.000 - Subtask 6 (23 puncte) :
1 ≤ N ≤ 1018
Exemplul 1:
Intrare
4 42
Ieșire
13
Explicație
Secvențele drăguțe formate din 4 numere distincte de la 1 la 4 sunt:
1 2 3 4
1 2 4 3
1 3 4 2
1 4 2 3
2 1 3 4
2 3 1 4
2 3 4 1
3 1 2 4
3 4 1 2
3 4 2 1
4 1 2 3
4 2 3 1
4 3 1 2
Exemplul 2:
Intrare
2000 10009
Ieșire
1295