SPPC - The SPP constant challenge

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.


Added by:Francky
Date:2013-02-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2016-05-23 16:23:56 Min_25
@Francky
Thank you. There were a lot of tricks to get a high score. :)

Last edit: 2016-05-23 16:24:43
2016-05-23 10:44:36 Francky
Congratulations to Min_25 ; You built warp drive !!! Amazing.
2014-12-14 20:07:39 quimey vivas
Thank you for this amazing problem! I keep working on this and I keep finding hacks to improve the speed.
--ans(Francky)--> Congratulations for all you great AC ; I saw you often. Thanks for the appreciation ; you're welcome.

Last edit: 2014-12-14 20:21:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.