FIBONOMIAL - Fibonacci Polynomial

## 题目描述 $\mathsf E\color{red}\mathsf{ntropyIncreaser}$ 喜欢数学，所以她的数学也非常好。 有一天，她想到了这样一个问题： 定义函数 $$\large D(n,x)=\sum\limits_{i=1}^nf_ix^i$$ 其中 $f_i$ 为 $\texttt{fibonacci}$ 数列，即： $$\large f_1=f_2=1$$ $$\large f_n=f_{n-1}+f_{n-2}\space (n\ge3)$$ 给定 $n,x$ ，求出 $D(n,x)$ 的值。 由于答案会非常大，所以要对 $10^9+7$ 取模。 然而 $\mathsf E\color{red}\mathsf{ntropyIncreaser}$ 觉得这个问题实在太sb了，随手造了几组数据就丢到了OJ上。 你能求出答案吗？ ## 输入输出格式 ### 输入格式 第一行一个正整数 $T$，表示数据组数。 接下来 $T$ 行，每行两个正整数 $n,x$，意义如题目描述。 ### 输出格式 输出 $T$ 行，每行一个整数，表示 $D(n,x) \text{ mod }10^9+7$ 的值。 ## 说明 【数据范围】 $1\le T \le 1000$ $0\le n,x \le 10^{15}$

**Problem description.** 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 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 description. - For each test case, output **D(n,x)%1000000007** in a seperate line.

1 
7 11

268357683