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² + 2x³ + 3x⁴ + 5x⁵ + 8x⁶ + ... + f(n)xⁿ

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¹⁵
• 0 ≤ x ≤ 10¹⁵

Example

Input:
1
7 11
Output:
268357683

Explanation

D(7, 11) = 11 + 11² + 2(11³) + 3(11⁴) + 5(11⁵) + 8(11⁶) + 13(11⁷) = 268357683.