/* 7/14/2018

* Problem: http://codeforces.com/problemset/problem/474/D

* Solution: Dp. dp[i] = dp[i-1] + dp[i-k]. One state can be transferred to from two sources: 1. eat only white flower from the i-k day 2. otherwise.

* Notes: 1. Remember to mod the MOD every time there’s a summing process.

2. The result of a mod can be negative.

* A little bit gibber-gabber:

For both the notes, I KNEW it but I now don’t..??

What is the point of everything..

*/

#include using namespace std; int main() { int t, k; cin >> t >> k; long long ind[100005] = {0}, sum[100005] = {0}; int MOD = 1000000007; for (int i = 0; i < k; i++) { ind[i] = 1; } for (int i = k; i <= 100005; i++) { ind[i] = (ind[i - 1] + ind[i - k]) % MOD; } sum[0] = 1; for (int i = 0; i a >> b; long long ans = (sum[b] - sum[a - 1]) % MOD; if (ans < 0) { ans += MOD; } cout << ans << endl; } return 0; }