Izumi este cel mai ghinionist om din univers — in fiecare zi îl pasc nenumărate probleme pe care nici nu le-ai putea imagina. Marele său noroc este Shikimori, care îl protejeaza zilnic de toate nenorocirile. Ghinionul de care trebuie protejat Izumi astăzi este un test la matematică!
Testul la matematică constă într-o singură întrebare, codificată printr-un număr natural N. Răspunsul la întrebare este orice expresie cu „sau”-uri exclusive și egaluri adevărată, care să conțină N simboluri.
Expresii cu „sau”-uri exclusive și egaluri. O expresie cu „sau”-uri exclusive și egaluri este un șir de doi sau mai mulți termeni separați prin câte un egal. Expresia se consideră a fi adevărată dacă toți termenii din care este formată sunt egali. Un termen este un șir de numere binare separate prin caracterul ^. Valoarea unui termen se consideră a fi „sau”-ul exclusiv pe biți al numerelor binare din care este format. Un număr binar este o înșiruire de cifre binare — se consideră că un număr binar are voie să înceapă cu cifra 0. Expresia trebuie să conțină măcar un egal.
Date de intrare
Prima linie conține numerele N și M separate printr-un spațiu, cu semnificația din enunț.
Date de ieșire
Se va afișa rezultatul cerut, modulo M.
Restricţii
- „Sau”-ul exclusiv pe biți este reprezentat în C/C++ prin operatorul
^. 1 ≤ N ≤ 5001 ≤ M ≤ 1 000 000 009Meste un număr prim
Subtask 1 (10 puncte)
1 ≤ N ≤ 11
Subtask 2 (15 puncte)
1 ≤ N ≤ 20
Subtask 3 (10 puncte)
1 ≤ N ≤ 50
Subtask 4 (25 puncte)
1 ≤ N ≤ 100
Subtask 5 (40 puncte)
1 ≤ N ≤ 500
Exemple
stdin
5 71
stdout
18
stdin
123 1000000007
stdout
275843270
Explicații
Pentru primul exemplu, expresiile adevărate sunt 000=0, 001=1, 00=00, 01=01, 0^0=0, 0^1=1, 0=000, 0=0^0, 0=0=0, 0=1^1, 10=10, 11=11, 1^0=1, 1^1=0, 1=001, 1=0^1, 1=1^0, 1=1=1.