beecrowd | 2893


By Fabiano S. Oliveira, UERJ BR Brazil

Timelimit: 1

Néchi is a very smart guy. He soon realized in the early years of his academic life that it is a good idea to look for patterns contained in the description of problems to memorize them. It is curious to observe the way he memorized the Fibonacci sequence; he thought as follows: let k be the number of letters "c" contained in "Fibonacci". Start the sequence by 0,1, ..., k-1 and obtain the next element of the sequence by the sum of the immediately preceding k elements. Develop a program to compute an arbitrary element of the Fibonacki sequence, as Néchi likes to call the problem.


The first line of the input is composed of the integer 1 ≤ T ≤ 10 which constitutes the number of test cases. The following T lines consist of the test cases, one per line. A test case consists of an integer 2 ≤ k ≤ 105 followed by an integer 1 ≤ N ≤ 2×105.


One line per test case should be written with the remainder of the division of the N-th element of the Fibonacki sequence by 1000007.

Input Sample Output Sample

2 5
7 5
7 10
8 64
10000 20000