Team Sigma and Fibonacci

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sigma and Fibonacci were two geeky friends. As ACM ICPC is near, they have started forming teams. Sigma loved summing series and Fibonacci loved playing with fibonacci numbers. They made Gopu as their ACM ICPC Coach. To train them up, Gopu gave them a challenge which will require both of their coordination to solve it. The challenge given by Gopu is described below:
Gopu gave them two numbers M and N and asked them to solve :
( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N.
Here x, y, z ≥ 0 and are integers.
Fibo is the Fibonacci number define as follows.
 Fibo[0] = 0
 Fibo[1] = 1
 Fibo[i] = Fibo[i1] + Fibo[i2] ∀ i ≥ 2 .
Now Gopu is wondering whether he will be able to determine whether they have calculated the solution of the problem correctly or not ! Help Gopu to find the correct answers , so that he can judge the solution for the team.
Input
First line of input contains an integer T denoting the number of test cases. Each test case begins in a new line, containing two space separated numbers representing M and N respectively.
Output
For each test case, output answer as stated above in a new line.
Constraints
 Sum of M over all test cases will be ≤ 10^{6}.
 0 ≤ N ≤ 10^{18}
 1 ≤ M ≤ 10^{5}
Example
Input:
4
100 3
100 4
100 9
100 10
Output:
6
36
66
60
Explanation for first test case:
In the first case, we have the following 10 terms for N = 3:
6 * 0*0*3*Fibo[0] * Fibo[0] * Fibo[3]
6 * 0*1*2*Fibo[0] * Fibo[1] * Fibo[2]
6 * 0*2*1*Fibo[0] * Fibo[2] * Fibo[1]
6 * 0*3*0*Fibo[0] * Fibo[3] * Fibo[0]
6 * 1*0*2*Fibo[1] * Fibo[0] * Fibo[2]
6 * 1*1*1*Fibo[1] * Fibo[1] * Fibo[1]
6 * 1*2*0*Fibo[1] * Fibo[2] * Fibo[0]
6 * 2*0*1*Fibo[2] * Fibo[0] * Fibo[1]
6 * 2*1*0*Fibo[2] * Fibo[1] * Fibo[0]
6 * 3*0*0*Fibo[3] * Fibo[0] * Fibo[0]
Here 6*1*1*1* Fibo[1] * Fibo[1] * Fibo[1] = 6 is only the nonzero term, the answer is 6.
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/SIGFIB 
Tags  aug14, devuy11, hard, mathematics 
Date Added:  23042014 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 