“Čížiček, čížiček, vtáčik maličký, povedz nám čížiček, ako brániť gól…”

Nuž, Joža táto filozofická otázka zaujala tiež. Až natoľko, že v jednom interview pre prestížny časopis DRB++, ktorého novinári pravidelne vyhľadávajú tie najvplyvnejšie osobnosti, povedal Jožo tento známy citát: “Prečo monštruózne obézni ľudia nie sú hokejoví brankári?”. Táto otázka už bola citovaná množstvom filozofov. Aj vďaka tomu je Jožo považovaný za jedného z najvplyvnejších mysliteľov modernej filozofie.

Dnes Joža trápi podobná, avšak trochu iná otázka. Na Wikipédii sa dočítal, že existujú trpaslíci aj obri. A aj trpaslíci, aj obri, môžu byť monštruózne obézni. Je však jasné, že monštruózne obézny trpaslík je oveľa menší, než monštruózne obézny obor. Jedna vec ich však všetkých spája a síce to, že sú rovnako širokí, ako vysokí.

A keďže Jožo sa vo svojom myslení nikdy nezastaví a vždy ide hlbšie a hlbšie, teraz ho zaujíma takáto otázka: koľkými spôsobmi je možné vyplniť veľkú hokejovú bránku monštruózne obéznymi ľudmi tak, aby sa do nej nedal streliť gól?

Úloha

Monštruózne obézni ľudia sú štvorcoví a majú rozmery $$1 \times 1$$, $$2 \times 2$$, $$3 \times 3$$, alebo $$4 \times 4$$ metre.

Máme veľkú hokejovú bránku s rozmermi $$4 \times n$$ metrov. Zistite, koľkými spôsobmi je možné ju úplne vyplniť monštruózne obéznymi ľuďmi (môžu stáť na sebe) tak, aby sa žiadni neprekrývali a aby nebolo ani trochu voľného miesta pre puk.

Keďže výsledok môže byť pomerne veľký, vypíšte jeho zvyšok po delení $$m$$.

Formát vstupu

Na vstupe sú na jednom riadku čísla $$n$$ a $$m$$ oddelené medzerou. Platí $$1 \leq n \leq 10^{16}$$ a $$1 \leq m \leq 10^7$$.

Formát výstupu

Vypíšte jeden riadok a na ňom jedno číslo: počet možností, ako zaplniť bránku $$4 \times n$$ monštruózne obéznymi ľuďmi modulo $$m$$.

Príklady

Input:

3 47

Output:

13

Input:

7 1000

Output:

29