You are given a positive integer \(X\) and your task is to find the summation of its perfect square divisors.
\(let \ X = {x_1}^{y_1} * {x_2}^{y_2} * {x_3}^{y_3} * .... * {x_n}^{y_n}.\)

Input format

The input is given in the following format

:\(n\\ x_1 \quad y_1\\ x_2 \quad y_2\\ x_3 \quad y_3\\ ...\\ x_n \quad y_n\)

Output format

Print one integer denoting the summation of the perfect square divisors of \(X\) modulo \(1e9 + 7\).

Constraints

 \(1 \leq x_i, y_i \leq 2\times {10^6} \\ 1 \leq n \leq 10^5\)