Fibonac^{k}i
By Fabiano S. Oliveira, UERJ 
Brazil
By Fabiano S. Oliveira, UERJ Brazil
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 |
|
5 |
3 |