All submissions for this problem are available.
After studying boolean algebra Leonardo defined L-binary numbers (which contains only 0’s and 1’s).
A binary number is L-binary if it does not contain K consecutive zeros and does not have leading zeros.
Find the number of L-Binary Numbers of length N.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Next T lines contains 2 integers N and K.
Print a line for each test case containing the required answer modulo 1000000007.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10000
- 1 ≤ K ≤ 10
Sample Input: 2
1 1 3 2 Sample Output: 1 3
|Time Limit:||- 1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO|
Fetching successful submissions