Furnicuta se deplaseaza pe o frunza reprezentata printr-o matrice patratica de n x n celule, pornind din coltul stanga-jos si dorind sa ajunga in coltul dreapta-jos, fara sa iasa de pe frunza. La un pas, ea poate urca (de la coltul stanga-jos al unei celule la coltul dreapta-sus) sau coborata (de la coltul stanga-sus la coltul dreapta-jos al unei celule), avansand mereu o coloana spre dreapta. Fie m numarul total de trasee valide. Determinati m modulo M.
- Date de intrare
- Se citesc pe o singura linie doua numere intregi n si M.
- Date de iesire
- Se afiseaza un singur numar intreg: restul impartirii lui m la M.
- Restrictii
- 0 <= n <= 60, 2 <= M <= 10^9
Exemple
Exemplul 1
Intrare
5 100
Iesire
42
Exemplul 2
Intrare
1 1000
Iesire
1