[Login|Register]
Problems

Status

Rank

Problem 1064
Poor Akagi
Time Limit: 10000ms
Memory Limit: 131072kb
Description
Akagi 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.
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.
Sample Input
3
3 1
2 2
4 3
Sample Output
10
14
443
Source
yuzhou627
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).