PROFILING  Profiling
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 spaceseparated integers N, K in a single line. (0≤N,K≤10^{5})
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
hide comments
mrm_196:
20190312 08:35:54
@fading: of course you should. If this algorithm was fast enough in the first place, there was no need to use a profiler :D 

fading:
20181218 18:07:49
With author's fibonaci algorithm, when N = 10^5, my program exceeds the time limit? So may I use other algorithm to overcome this or what can I do ? 

DOT:
20180817 23:12:06
Thanks @wangchong756, I'd missed that case. 

spaceman_spiff:
20180613 18:08:13
Last edit: 20180613 18:19:35 

mrm_196:
20180523 08:17:29
the problem with the consraints is fixed, sorry for that 

prakash1108:
20180519 13:36:40
Thanks @wangchong756


praney_rai:
20180519 12:27:19
You should specify constraints atleast _ 

Vipul Srivastava:
20180518 12:00:38
Last edit: 20180518 16:29:21 
Added by:  MRM 
Date:  20180518 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  SBU Newbies Programming Contest 2018 