Akagi is not only good at basketball but also good at math. Recently, he got a sequence Ln from his teacher. Ln is defined as follow:
$$\Large L(n)=\begin{cases}
2 & \text{ if } n=0 \\
1 & \text{ if } n=1 \\
L(n-1)+L(n-2) & \text{ if } n>1
\end{cases}$$
And Akagi’s teacher cherishes Agaki’s talent in mathematic. So he wants Agaki to spend more time studying math rather than playing basketball. So he decided to ask Agaki to solve a problem about Ln and promised that as soon as he solves this problem, he can go to play basketball. And this problem is:
Given N and K, you need to find \(\Large\sum\limits_{0}^{N}L_i^K\)
And Agaki needs your help.
Input
This problem contains multiple tests.
In the first line there’s one number T (1 ≤ T ≤ 20) which tells the total number of test cases. For each test case, there an integer N (0 ≤ N ≤ 10^18) and an integer K (1 ≤ K ≤ 100000) in a line.
Output
For each test case, you need to output the answer mod 1000000007 in a line.
