7. Obézni brankári

“Číž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