#include<bits/stdc++.h>
using namespace std;
int main()
{
long int i,j,dp[11][10001];
for(i=1;i<=10;i++)
{
dp[i][0]=1;
dp[i][1]=1;
for(j=2;j<=10000;j++)
{
if(j>i)
{
dp[i][j]=(2*dp[i][j-1]-dp[i][j-i-1]+1000000007)%1000000007;
}
else
{
dp[i][j]=(2*dp[i][j-1])%1000000007;
}
}
}
int t,n,p;
cin>>t;
while(t--)
{
cin>>n>>p;
cout<<dp[p][n]<<endl;
}
}
- Problem Description
Two letter strings are the strings consisting of only two letters “X” and “Y”. A string is “super two letter string” if
a) It does not have leading “X” letters.
b) It does not contain P consecutive “X” letters.
Your task is to find total number of Super two letter strings of length N.
Input :
The first line contains the number of test cases T . Each test case consists of two space separated integers – N and P .
Output :
For each test case output total number of Super two letter strings of length N modulo 1000000007(10^9+7).
Constraints :
1 <= T <= 100
1 <= N <= 10^4
1 <= P <= 10 - Test Case 1
Input (stdin)2
2 1
4 2
Expected Output1
5 - Test Case 2
Input (stdin)7
2 3
1 4
5 1
6 3
1 3
4 2
7 2
Expected Output2
1
1
24
1
5
21