One day, Homer was bored in his house and decided to go in a journey to discover the lands of Springfield.The lands of Springfield is an infinite grid. Homer's house is located at cell (0, 0) and his journey consistedof N steps, where each step is either move one cell right or one cell down. 

Being bored already, Homer didn't want his journey to be boring as well. He decided he won't move inthe same direction for more than K consecutive steps. Thus, a journey is considered to be interesting iffor each K+1 consecutive steps Homer has moved in both directions. 

                   Figure 1: Example with N=5 and K=2 (first test case). 

Given N and K, count the number of interesting journeys Homer can make. Two Journeys are considered different if for some i the ith step in the first Journey differs from that of the second Journey. Since the number can be large, print it modulo 1,000,000,007. 

Input 

 Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 500), followed by T test cases.Each test case will be presented on a single line containing two integers separated by a single space.The first integer will denote the number of steps in Homer's journey N, followed by the second integer K representing the maximum number of consecutive steps Homer can take while moving in the same direction, where (0 ≤ N ≤ 1e5) and (0 ≤ K ≤ 1e5).Output For each test case,

 output 

a single line denoting the number of different journeys Homer can make modulo1,000,000,007. 

样例输入复制

2
5 2
10 1

样例输出复制

16
2

题意：

只能向下走或向右走，在连续 k 步内不能向同一方向走，问走 n 步的策略数

思路：

注意n == 0 时方案数为1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

ll dp[N];

int main()
{
    int t, n, k;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        dp[1] = 1;
        ll sum = 1;
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = sum % mod;
            if(i > k)
            {
                sum = (sum - dp[i - k] + mod) % mod;
            }
            sum = (sum + dp[i]) % mod;
        }
        if(!n)
            cout<<1<<'\n';
        else
            cout<<sum * 2 % mod<<'\n';
    }
    return 0;
}