思路

二分 + 前缀和。

一个数的因子数等于其 每个质因子 $p_i$ 的数量加1 的乘积，即 $\prod\limits_{i} (cnt_{p_i}+1)$

$q$ 次询问，要求我们单次查询需要控制在 $O(\log n)$ 内。

因为 $10$ 以内只有 $2,3,5,7$ 这 4 个质数，所以可以对这 4 个质数预处理前缀和

题目描述

小美拿到了一个数组，她有$q$次查询，每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗?

注:由于数组元素过多，所以是按连续段的方式给定。例如，[1,1,2,3,3,3]有2个1，1个2，3个3，因此表示为<2,1>,<1,2>,<3,3>。

输入描述

第一行输入两个正整数$n,m$，代表数组的大小，以及连续段的数量。 接下来的$m$行，每行输入两个正整数$u_i,v_i$，代表一段区间内有$v_i$个$u_i$

接下来的一行输入一个正整数$q$，代表询问次数。 接下来的$q$行，每行输入两个正整数$l,r$，代表询问的是第$l$个数到第$r$个数的乘积的因子数量

$1\le n\le 10^{14}$

$1\le m,q\le 10^5$

$1\le u_i\le 10$

$1\le v_i\le 10^9$

$1\le l,r\le n$

保证所有的$v_i$之和恰好等于$n$

输出描述

输出$q$行，每行输出一个整数，代表最终的乘积因子数量。由于答案可能过大，请对$10^9+7$取模

样例

输入

6 3
1 2
2 1
3 3
2 
1 3
2 6

输出

2
8