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.