You are given ${D}$ datasets where each dataset is in the form of two integers, $m$ and ${a}$, such that:
$n=\prod\limits_{i=1}^m p_i^{a+i},\text{where}~p_i~\text{is the}~i^{th}~\text{prime}.$

For each dataset, find and print the following on a new line:

$\sum_{d|n}\sigma_0(d)$

where $\sigma_0(x)$ is the count of divisors of ${x}$. As the answer can be quite large, print the result of this value modulo $(10^9+7)$.

Input Format

The first line contains an integer, ${D}$, denoting the number of datasets.

Each line ${i}$ of the ${D}$ subsequent lines contains two space-separated integers describing the respective values of $m_i$ and $a_i$ for dataset ${i}$.

Constraints

$1\leq D\leq10^5$
$1\leq m\leq10^5$
$0\leq a\leq10^5$

Output Format

For each dataset, print a single integer denoting the result of the summation above modulo $(10^9+7)$ on a new line.

Sample Input
3
2 0
3 0
2 4

Sample Output
18
180
588

Explanation

For the first dataset where $m=2$ and ${a}=0$,
$\begin{aligned}&n=2^1\times3^2\\\Rightarrow&2\times9\\\Rightarrow&18$
$18}$ has the following divisors: $\{1,2,3,6,9,18\}$. Therefore, the result is:

$\begin{aligned}&\sigma_0(1)+\sigma_0(2)+\sigma_0(3)+\sigma_0(6)+\sigma_0(9)+\sigma_0(18)\\ \Rightarrow&1+2+2+4+3+6\\ \Rightarrow&18\end{aligned}$

Thus we print the value of $18\%(10^9+7)=18$ on a new line.

见题面

见题面