題干：

We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be represented as a sequence of several flowers, some of them white and some of them red.

But, for a dinner to be tasty, there is a rule: Marmot wants to eat white flowers only in groups of size?k.

Now Marmot wonders in how many ways he can eat between?a?and?b?flowers. As the number of ways could be very large, print it modulo?1000000007?(109?+?7).

Input

Input contains several test cases.

The first line contains two integers?t?and?k?(1?≤?t,?k?≤?105), where?t?represents the number of test cases.

The next?t?lines contain two integers?ai?and?bi?(1?≤?ai?≤?bi?≤?105), describing the?i-th test.

Output

Print?t?lines to the standard output. The?i-th line should contain the number of ways in which Marmot can eat between?ai?and?bi?flowers at dinner modulo?1000000007(109?+?7).

Examples

Input

3 2 1 3 2 3 4 4

Output

6 5 5

Note

• For?K?=?2?and length?1?Marmot can eat (R).
• For?K?=?2?and length?2?Marmot can eat (RR) and (WW).
• For?K?=?2?and length?3?Marmot can eat (RRR), (RWW) and (WWR).
• For?K?=?2?and length?4?Marmot can eat, for example, (WWWW) or (RWWR), but for example he can't eat (WWWR).

題目大意：

把紅花和白花擺成一排，并且要求若出現白花，它們連續的數量必須是k的倍數。

給我們 n，接下來的n次詢問。和k???(n,k<100000)

每行 一個 a和b。

設f(k)為長度為k的滿足條件的一排花 的 可能的數量

最后求f(a)+f(a+1)+...+f(b)

（不要理解成給定一個區間一共b個，去求a到b的，而是一共a個，一共a+1個....一共b個? 的可能情況的和）

另一個題目大意：

話說某個幸運的小伙伴X拿到了kevin女神送的蛋糕，然而他的吃法非常奇特，他獨創了兩種吃蛋糕的辦法：一、一次吃一整個蛋糕；二、一次吃k個蛋糕。

那么，當蛋糕數量為x1到x2之間時，一共能有幾種不同的吃法呢？

由于答案很大，輸出結果mod?1000000007的值

解題報告：

? ?直接dp就完事了，然后再維護一個前綴和。如果按照第一種題意，那就看AC代碼2，第二種題意就看AC代碼1。但是第一種題意可以轉化成第二種，因為不管什么花其實可以看成是同一種，只不過有兩種擺法就是了。

AC代碼1：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll dp[MAX],ans[MAX]; const ll mod = 1e9 + 7; int main() {int t,k;cin>>t>>k;dp[0]=1;for(int i = 1; i<MAX; i++) {dp[i] = dp[i-1];if(i >= k) dp[i] += dp[i-k];dp[i]%=mod;}int x,y;for(int i = 1; i<MAX; i++) {ans[i] = ans[i-1] + dp[i];}while(t--) {scanf("%d%d",&x,&y);printf("%lld\n",(ans[y] - ans[x-1] + mod)%mod);}return 0 ;}

AC代碼2：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll dp[MAX][2],ans[MAX];//dp[][0]代表紅花,dp[][1]代表白花 const ll mod = 1e9 + 7; int main() {int t,k;cin>>t>>k;dp[0][0]=1;dp[0][1]=0;for(int i = 1; i<MAX; i++) {dp[i][0] = dp[i-1][0];dp[i][1] = dp[i-1][1];if(i >= k) dp[i][1] += dp[i-k][0] + dp[i-k][1];dp[i][1]%=mod;dp[i][0]%=mod;}int x,y;for(int i = 1; i<MAX; i++) {ans[i] = ans[i-1] + dp[i][0] + dp[i][1];}while(t--) {scanf("%d%d",&x,&y);printf("%lld\n",(ans[y] - ans[x-1] + mod)%mod);}return 0 ;}

?

總結

以上是生活随笔為你收集整理的【CodeForces - 474D】Flowers （线性dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。