#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