FIBONOMIAL  Fibonacci Polynomial
Problem description.
The Fibonacci numbers defined as f(n) = f(n1) + f(n2) where f0 = 0 and f1 = 1.
We define a function as follows D(n,x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 +...+f(n)x^n
Given two integers n and x, you need to compute D(n,x) since the output can be very large output the result modulo 1000000007 (1e9+7) .
Input
Input description.
 The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.  The first line of each test case contains two integers n and x as described above.
Output
Output description.
 For each test case, output D(n,x)%1000000007 in a seperate line.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ T ≤ 1000
 0 ≤ n ≤ 10^15
 0 ≤ x ≤ 10^15
Example
Input: 1 7 11 Output: 268357683
Explanation
D(7,11) = 11 + 11^2 + 2(11^3) + 3(11^4) + 5(11^5) + 8(11^6) + 13(11^7) = 268357683
hide comments
sdeven_0245:
20170518 08:12:20
i dont know why iam getting wrong answer


Shubham Jadhav:
20170503 03:42:24
I am getting NZEC error in python. any idea why??


ks1999:
20170430 17:12:12
is there formula for this problem? 

candide:
20170430 01:50:33
Pleasant exercice and refering to Project Euler helps a lot. Hint: find a closed formula for D(x,n).


akshayjhamb2:
20170423 17:59:48
PVSM Praveen can u check my solution?


amrsaber:
20170415 18:07:19
The equation in the reply is not the same as the one in the question


amrsaber:
20170415 15:24:11
The definition should end with


mahmud2690:
20170414 21:16:40
Check your test cases, there are cases N, X < 1 or N, X > 1.e15.

Added by:  PVSM Praveen 
Date:  20170414 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ProjectEuler 