A positive integer is given by its prime factorization \(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}\). Compute the number of positive divisors of \(n\).

Input

The first line contains \(k\). Each of the next \(k\) lines contains a prime \(p_i\) and its positive exponent \(e_i\).

The input satisfies:

• \(1 \le k \le 100\)
• \(2 \le p_i \le 10^5\)
• \(1 \le e_i \le 10^5\)
• The p_i values are distinct primes.

Output

Print the number of divisors modulo \(1,000,000,007\).

Example

Input

1
15212 89287

Output

89288