SPOJ.com - Problem FIBONOMIAL

FIBONOMIAL - Fibonacci Polynomial

no tags

The Fibonacci numbers defined as f(n) = f(n-1) + f(n-2) 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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains two integers n and x as described above.

Output

For each test case, output D(n, x) % 1000000007 in a separate line.

Constraints

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.

Submit solution!

hide comments



	David: 2022-01-12 21:14:07 @ks1999 Yes, there is a closed form formula for D(n,x). Last edit: 2022-06-17 23:15:00
	sdeven_0245: 2017-05-18 08:12:20 i dont know why iam getting wrong answer
	Shubham Jadhav: 2017-05-03 03:42:24 I am getting NZEC error in python. any idea why?? Re ==> There are Accepted codes in python too.. Last edit: 2017-05-10 06:25:58
	ks1999: 2017-04-30 17:12:12 is there formula for this problem?
	candide: 2017-04-30 01:50:33 Pleasant exercice and refering to Project Euler helps a lot. Hint: find a closed formula for D(x,n). Easy to code in Python, thanks to the pow function. The problem description is good. Perhaps, as the comments suggest, it would be clearer to declare D(n,x) as: D(n,x) = 0x^0+1x^1 +1* x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 +...+f(n)x^n. On the other hand, about the input, the description states "The first line of each test case contains two integers n and x as described above": since each test case is compound of exactly ONE line, refering to the "first" one adds nothing ;) Last edit: 2017-04-30 01:51:15*
	akshayjhamb2: 2017-04-23 17:59:48 PVSM Praveen can u check my solution? ==> Re : I Checked it, your intermediate results overflows, that's what all i can say. Last edit: 2017-04-24 16:52:47
	amrsaber: 2017-04-15 18:07:19 The equation in the reply is not the same as the one in the question In The question, a2 = 1 and there is no a0 ==> Re : Its fibonacci series, a0=0,a1=1,a2=1,a3=2 and so on... since here a0 = 0 0 + 1x + 1x^2 + 2x^3 + .... f(n)x^n Last edit: 2017-04-15 18:29:10
	amrsaber: 2017-04-15 15:24:11 The definition should end with ... + f(n-1) x^(n) Right ? ===> Re : f(0) = 1 and f(1) = 1, the equation a0+a1x+a2x^2.... anx^n where a0 = f(0) and a1 = f(1) and so on... hence f(n)x^n Last edit: 2017-04-15 15:27:31
	mahmud2690: 2017-04-14 21:16:40 Check your test cases, there are cases N, X < 1 or N, X > 1.e15. ==> Re : Yes , sorry for the inconvenience, N , X can be 0. Please see updated constraints. Last edit: 2017-04-15 08:09:27

Submit solution!

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