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.2kBpython3 code got 4500 points,
whereas my old 2kBC one got 160000 points. (Edited 20170211, 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 uniformrandomly 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 SPPconstantspeed.
Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file.
hide comments
Min_25:
20160523 16:23:56
@Francky


Francky:
20160523 10:44:36
Congratulations to Min_25 ; You built warp drive !!! Amazing. 

quimey vivas:
20141214 20:07:39
Thank you for this amazing problem! I keep working on this and I keep finding hacks to improve the speed.

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