Profiling: In software engineering, profiling ("program profiling", "software profiling") is a form of dynamic program analysis that measures, for example, the space (memory) or time complexity of a program, the usage of particular instructions, or the frequency and duration of function calls. Most commonly, profiling information serves to aid program optimization. - Wikipedia

Arthur and Jacob are newly introduced to the programming world and they are trying hard for Newbies contest. Yesterday, they learned about recursive functions and Fibonacci sequence. They tried to implement the function themselves so they wrote the following code:

          int fibonacci (int N)
          {
              if(N < 2)
                  return N;
              return fibonacci(N - 1) + fibonacci(N - 2);
          }

But this program works slowly when N is a large number. They traced the program and found the cause of this problem. Take a look at the following picture:

If you want to calculate Fibonacci(6), Fibonacci(3) will be calculated multiple times!

They want to know how serious this problem can be, so they need a profiler to calculate such a thing for them.

Your task is to provide the profiler which receives two integers N, K and tells them if they call Fibonacci(N) how many times Fibonacci(K) will be calculated (according to their code).

Input

The first line of input indicates the number of test cases (There will be at most 100 test cases)

For each test case, there are two space-separated integers N, K in a single line. (0≤N,K≤10⁵)

Output

For each test case, print the number of times Fibonacci(K) will be calculated, if we call Fibonacci(N). Since the result can be very large, print the result modulo (Mod %) 1000000007.

Example

Input:
5
6 6
6 3
6 2
100000 3
5 10
Output:
1
3
5
855252772
0