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 ≤ 500
• 1 ≤ M ≤ 1 000 000 009
• M este 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.