| [Home|Training|Problems|Contests|C Language] | [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
|