链接：https://ac.nowcoder.com/acm/contest/3006/F

在ACM比赛里，除了CE以外都是有效的提交。每一个提交都会有其评测的结果，或是AC，或是RJ（Rejected，包含各种不通过的情况）。往往一个人上去提交的时候，总有一个队友会坐在边上等着结果。那个人，往往都是只读题不写题的云选手~

牛牛战队里也有这样的云选手——牛能。当牛能看到有效提交得到了AC以后，都会大呼一声“你好能啊！”，反之，如果得到了RJ的话，就会化身为喷子，说xx句“你能不能行啊！”。大家比赛的都十分紧张，这样的大声呼喊未免会引起旁边队伍的注意。

当然牛牛战队交题的时候也很小心，一旦这一发出现了RJ，下一发有效提交一定能获得AC。

比赛结束了以后，旁边的一支队伍愤怒的跑过来说：你们比赛的时候吵不吵啊，一直在这大吼，吼了这么多句！

激烈的争吵引起了吃瓜群众的注意，吃瓜群众问道：吼了多少句啊，这么讨厌的吗

“啊……我也记不清了，大概是在[L,R][L,R]这个区间吧”

作为吃瓜群众的你，想根据这个信息算出，这个队伍有多少种有效提交结果序列的可能呢？

输入描述:


 

输入数据包括单组数据、多组询问。输入第一行包含一个整数x(2 \leq x \leq 100\,000)x(2≤x≤100000)，表示牛能在RJ状态下会说“你能不能行啊！”的句子数量。

第二行包括一个整数Q(1 \leq Q \leq 10^5)Q(1≤Q≤105)，表示询问数量。

接下来QQ行，每行包括两个整数L,R(1 \leq L \leq R \leq 100\,000)L,R(1≤L≤R≤100000)，表示每次询问下句子的区间数。

输出描述:

对于每组数据，在一行内输出一个整数，表示牛牛战队提交结果的可能性。由于结果可能很大，请对1\,000\,000\,0071000000007取模。

示例1

输入

复制

3
3
3 3
1 4
1 5

输出

复制

2
7
11

说明


 

第一组询问：可以是三个AC，或者一个RJ。

第二组询问：可以是1~4个AC，一个AC和一个RJ（共2种顺序），或者一个RJ。

第三组询问：可以有1~5个AC，两个AC和一个RJ（共3种顺序），一个AC和一个RJ（共2种顺序），或者一个RJ。

备注:

AC RJ AC AC 和 AC AC AC RJ 虽然都是3个AC，1个RJ，但是因为提交顺序的不同，视为不同种类。

我真是太菜了，把动态规划写成规律题qaq

代码：

#include<bits/stdc++.h>
using namespace std;
long long t,n,l,r,x,s,k;
long long mod=1e9+7;
long long dp[100001][3],sum[1000001];
map<long long,long long>m[1000001],sm;
int main()
{
	cin>>x;
	for(int i=1;i<=x-1;i++)
	{
		dp[i][1]=1;
		dp[i][0]=0;
	}
	dp[x][1]=1;
	dp[x][0]=1;
	for(int i=x+1;i<=100001;i++)
	{
		dp[i][1]=(dp[i-1][1]+dp[i-1][0])%mod;
		dp[i][0]=dp[i-x][1];
	}
	sum[0]=0;
	for(int i=1;i<=100001;i++)
	{
		sum[i]=sum[i-1]+(dp[i][0]+dp[i][1])%mod;
		sum[i]%=mod;
	}
	cin>>t;
	while(t--)
	{
		cin>>l>>r;
		s=0;
		s=sum[r]-sum[l-1];
		s%=mod;
		cout<<(s+mod)%mod<<endl;
	}
}