Warning

This task can be 'easily' solved with a O(log(N)) algorithm. You'll have to work on the constant to get more points. This task should help you to try some speed improvements for problems like SPP, Snaky Numbers, or Crack the Safe which share the context. Here, the keypad had been carefully chosen... Have fun.
You don't need to solve the whole input, just as many cases as you can. Not all, it could be impossible. You will get one point per case.
For your information, my 1.2kB-python3 code got 4500 points, whereas my old 2kB-C one got 160000 points. (Edited 2017-02-11, after compiler changes).

The Safe and its Lock

Since 1984, there's too many terrorists, so Leo have a very secured safe with a very long password. He uses it to store all other passwords he needs. The only restriction of the password for that safe is that every pair of neighboring keys in the password is adjacent on the keypad. Adjacent means that the keys share a common edge.
The secure door have a 6×6 lock which resembled this :

A B C D E F
G H I J K L
M N O P Q R    [Enter]
S T U V W X
Y Z 1 2 3 4
5 6 7 8 9 0

[Enter] is not part of the password.

Now, given the length of the password, we just would like to know how many different possibilities are there for the password.

Input

The input consists of 666666 lines.
In each the 666666 lines there are two integers N, M.

Output

For as many test cases you can, on a single line, print the number of different passwords of length N. As the answer could be an enormous number, output the answer modulo M.

Example

Input:
1 10
2 100
987654321123456789 1000000000
[...]

Output:
6
20
831617808

Explanations

For a one key password, there are 36 possibilities, answer modulo 10 is 6.
For a two keys password, there are 120 possibilities, answer modulo 100 is 20.
For the last case, the answer has around 5×10¹⁷ digits, the nine last ones are 831617808.

Constraints

1 <= N <= 10^18
2 <= M <= 10^9

There's one input file, and data are uniform-randomly chosen in their range.

Score

As in the example, if you can output the 3 first correct answers, your score will be 3 points.
No need to solve all the input, the minimum is 1 ; every solver in 'any' language will be able to check his SPPconstant-speed.

Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file.