题目描述

质数是只含\(1\)和自己作为正因数的数，在数学中质数有许多美妙的性质可以被利用，同时质数本身也有很多问题值得人们去研究。

Kiana非常喜欢数学，尤其是喜欢质数，并经常做一些和质数相关的小游戏。某一天，她写下了\(n\)个数，并定义函数\(Cnt(p)\)表示这\(n\)个数中能被质数\(p\)整除的数的个数。对于一个不是质数的数\(a\)，Kiana定义\(Cnt(a)\)的值为\(0\)。

现在Kiana想知道这个函数某一段区间上的取值之和，即对于一组给定的\(L,R\)，她希望知道\(\sum_{i=L}^RCnt(i)\)等于多少。不仅如此，Kiana还希望给出多组\(L,R\)，并对每一组都得到一个这样的答案。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数\(n\)和\(m\)，分别表示Kiana写下的数的数量，以及提出的询问组数。

第二行包含\(n\)个正整数，表示Kiana写下的\(n\)个数的值。

接下来\(m\)行，每行包含两个正整数\(L\)和\(R\)，表示Kiana提出询问的区间。

输出格式

输出共\(m\)行，每行包含一个正整数，表示每组询问的答案，由于答案可能很大，只需要输出其对\(10^9+7\)取模后的结果即可。

输入输出样例

输入样例#1：

5 3
4 6 7 9 11 
2 3
1 4
1 5

输出样例#1：

4
4
4

输入样例#2：

prime2.in

输出样例#2：

prime2.ans

样例解释

Kiana一共写下了\(5\)个数：\(4,6,7,9,11\)，并进行了\(3\)次询问：

• \([2,3]\)中共有两个质数\(2\)和\(3\)，其中\(2\)能够整除\(4\)和\(6\)，故\(Cnt(2)=2\)，而\(3\)能够整除\(6\)和\(9\)，故\(Cnt(3)=2\)，所以\(\sum_{i=2}^3Cnt(i)=4\)

• \([1,4]\)中也只有两个质数\(2\)和\(3\)，故这一问答案和上一问相同，即\(\sum_{i=1}^4Cnt(i)=4\)

• \([1,5]\)中共有三个质数\(2,3\)和\(5\)，但是\(5\)不能整除任何一个Kiana写下的数，故\(Cnt(5)=0\)，所以这一问答案和前两问相同，即\(\sum_{i=1}^5Cnt(i)=4\)

数据范围

对于\(10\%\)的数据，保证\(1\leq n\leq 10,1\leq m\leq 10\)。

另有\(20\%\)的数据，保证\(1\leq n\leq 10,1\leq m\leq 10^6\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 1000,1\leq m\leq 10\)。

另有\(20\%\)的数据，保证\(1\leq n\leq 1000,1\leq m\leq 10^6\)。

另有\(15\%\)的数据，保证\(1\leq n\leq 10^6,1\leq m\leq 10\)。

另有\(25\%\)的数据，保证\(1\leq n\leq 10^6,1\leq m\leq 10^6\)。

对于\(100\%\)的数据，保证Kiana写下的数不大于\(10^7\)，且\(1\leq L\leq R\leq 10^7\)。

此外共有\(35\%\)的数据，保证\(R-L\leq 50\)。