Perfect divisors

★★★★★

3.2

5 votes

Modular arithmetic, Combinatorics, Number theory, Prime Factorization, Basics of Combinatorics, Algorithms, Modular exponentiation, Math

Details

Submissions

Discussion

Editorial

Problem

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$

Sample Input

2
2 2
3 1

Sample Output

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

the sampe input corresponds to X = 2^2 * 3^1 = 12, which has these divisors : 1, 2, 3, 4, 6, 12.
Among these divisors these are pefect square : 1, 4, so the answer is 1 + 4 = 5

Contributers:

ahmad salah

Arpa PoorAkhavan