1700*D. Flowers（DP&&前缀和&&预处理打表）

                                      dp[ i ] = 2，i==k

                                      dp[ i ] = dp[ i-1 ]+dp[ i-k ]，i>k

        并且每次询问数据范围都为1e5，所以预处理前缀和。

        注意，因为每次都取模mod，可能导致最后答案小于 0 的情况，所以此时需要加一个mod。

#include
using namespace std;
#define int long long
const int N=1e5+5,mod=1e9+7;
int t,k,dp[N],sum[N];
signed main(){
	scanf("%lld%lld",&t,&k);
	dp[1]=1;
	for(int i=1;i<=k;i++){
		dp[i]=1;
		sum[i]=sum[i-1]+1;
	}
	dp[k]+=1;
	sum[k]+=1;
	for(int i=k+1;i<=1e5;i++){
		dp[i]=(dp[i-1]+dp[i-k])%mod;
		sum[i]=(sum[i-1]+dp[i])%mod;
	}
	while(t--){
		int a,b;
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",(sum[b]-sum[a-1]+mod)%mod);
	}
	return 0;
}