Problem Statement

Consider the following problem $X$.

Problem $X$

For a given integer, find the sum of the positive divisors of that integer.

You are given integer sequences $P$ and $e$ of length $L$. The elements of $P$ are distinct prime numbers. Here, let $N=\prod_{i=1}^{L} P_i^{e_i}$ $(= P_1^{e_1}\times P_2^{e_2}\times \dots \times P_L^{e_L})$.

For every positive divisor of $N$, find the answer to problem $X$ when given that number, and output the sum of these answers. Since the answer can be very large, output the remainder when divided by $(10^{9}+7)$.

Constraints

• $1\leq L\leq 2\times10^{5}$
• $1\leq P_i,e_i\leq 10^{9}$
• All inputs are integers
• All $P_i$ are prime numbers
• If $i\neq j$, then $P_i\neq P_j\;(1\leq i,j\leq L)$

Input

$L$
$P_1\; e_1$
$P_2\; e_2$
$\vdots$
$P_L\; e_L$

Output

Output the remainder when the answer is divided by $(10^{9}+7)$. Print a newline at the end.

Sample

2
2 2
3 1

55

1
167 1

169

10
914260891 350096548
887686339 192497607
786328273 878092875
735623069 355760739
129154631 798229587
427094807 82130028
520933789 204087959
641996039 29097051
278883373 321445979
447005677 226153917

326821356