猫史档案馆

题目描述：
中世纪时期，[万圣节]有一个流行的活动——制作“灵魂之饼” 。

与现代的”不给糖果就捣蛋”活动非常相似 。

胖虎，今年8岁，身高一米八，作为附近村子远近闻名的熊孩子，在万圣节即将来临之际，自然准备参与到这场活动中来准备到其他家庭要糖。每一次讨糖要么得到糖，要么被拒绝，当要到糖的时候，会大声说出 不给糖就捣蛋 ,反之，如果得不到，化身为熊孩子，说x句 我要捣乱 。由于他彪悍的身躯，人们都畏惧他，当他被拒绝后下次再要糖的时候，人们都会给他。

万圣节结束了以后，旁边的孩子们看到他手里那么多糖，羡慕了起来，问他喊了多少句。

胖虎:“忘记了，大概是在 [L,R] 这个范围吧!"

作为聪明的你，想根据这个信息算出，这个胖虎有多少种喊的可能呢？

输入描述
输入数据包括单组数据、多组询问。输入第一行包含一个整数x，表示胖虎在被拒绝状态下会说 我要捣乱 的句子数量。

第二行包括一个整数Q，表示询问数量。

接下来Q行，每行包括两个整数L,R，表示每次询问下喊话的区间数。

输出描述
对于每组数据，在一行内输出一个整数，表示胖虎喊话的可能性。由于结果可能很大，请对1000000007取模。

样例输入
3
3
3 3
1 4
1 5
样例输出
2
7
11

提示
不给糖就捣蛋和 我要捣乱对应数量一致时，但喊的顺序不一样，视为不同可能

例如：当x=1时，2次不给糖就捣蛋，1次我要捣乱 有以下三种顺序

我要捣乱 不给糖就捣蛋 不给糖就捣蛋

不给糖就捣蛋 我要捣乱 不给糖就捣蛋

不给糖就捣蛋 不给糖就捣蛋 我要捣乱

样例解释
第一组询问： 可以是三次不给糖就捣蛋，

或者一次我要捣乱。

第二组询问： 可以是1-4次不给糖就捣蛋， 一次不给糖就捣蛋和一次我要捣乱（共2种顺序）， 或者一次我要捣乱。

第三组询问： 可以有1-5次不给糖就捣蛋， 两次不给糖就捣蛋和一次我要捣乱（共3种顺序）， 一次不给糖就捣蛋和一次我要捣乱（共2种顺序）， 或者一次我要捣乱。

数据范围
对于30%的数据 : x=1

对于50%的数据 : x<20,Q<30

对于100%的数据 : 1<=x<=10^5,1<=Q<=10^5,1<=L<=R<=10^5 

PS:可以把代码发在评论区，其他与上期相同