Harit wants to climb ladder having n steps but he want to climb only in step of 2 and 5. Now he felt boring repeating same thing again and again. So he discovered new way, now each time Harit wants to climb in step of k also. In other words he can use steps of 2, 5 or k to climb the ladder. So Harit want to calculate number of different ways to reach at cur step , where k and cur are integers . Although Harit is intelligent yet lazy so he wants your help to calculate number of ways. As number of ways could be too large so he wants you to output it modulo 1000000007 (10^9 + 7) .
Input :
First line consists two space separated integers t and n as number of test cases and total steps in ladder. Each of t lines contains two space separated integers cur and k .
Output :
For each test case output an integer calculated number of ways modulo (10^9 + 7) .
Constraints
1 <= t <= 100000
1 <= n <= 1000000
5 <= k <= 1000000000
cur <= n and sum of all cur such that ( cur >= k ) will not exceed 10000000 .
In first test case there is only 1 way to reach at 6th step i.e. taking step of (2,2,2) . In second test case there are 2 ways to reach at 6th step i.e. taking step of (2,2,2) or directly step of 6 in third test case there are 5 ways to reach at 9th step i.e taking step (2,2,5) , (2,5,2) , (5,2,2) , (2,7) , (7,2) .
