该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给一个长度为 $n$ 的排列，满足 $p_i=i$ 。

有 $q$ 次询问，每次询问给定一个区间，从区间中挑选任意多个元素（但是不能挑选相邻的两个元素）有多少种挑选方法？

输入格式

第一行两个整数 $n,q$

接下来 $q$ 行，每行两个整数 $l,r$，满足 $1\leq l\leq r\leq n$。

输出格式

每个询问输出一个答案，对 $10^9+7$ 取模。

样例 #1

样例输入 #1

10 3
1 10
2 5
3 4

样例输出 #1

144
8
3

提示

对于 $30\%$ 的数据满足 $1\leq n,q\leq 1000$

对于 $70\%$ 的数据满足 $1\leq n,q\leq 10^5$

对于 $100\%$ 的数据满足 $1\leq n\leq 10^9,1\leq q\leq 10^5$。