Time Limit: 10000ms
Memory Limit: 131072kb
DescriptionAkagi is not only good at basketball but also good at math. Recently, he got a sequence Ln from he teacher. Ln is defined as follow:
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:
And Agaki needs your help.
InputThis 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.
OutputFor each test case, you need to output the answer mod 1000000007 in a line.
3 3 1 2 2 4 3
10 14 443