Changyoung's Password
Time limit5sMemory limit128 MB
Given the prime factorization of a huge n, compute the sum of a+b over all unordered pairs with lcm(a,b)=n, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Number theory, Math, Combinatorics
- Solved
- No attempts yet
Problem
Changyoung uses a function f to create passwords.
For a positive integer n, f(n) is defined as follows: find every unordered pair (a, b) with a ≤ b whose least common multiple is exactly n, and add up a + b over all such pairs.
For example, the pairs whose least common multiple is 6 are (1, 6), (2, 6), (2, 3), (3, 6), and (6, 6) — five in total — so
f(6) = (1+6) + (2+6) + (2+3) + (3+6) + (6+6) = 7 + 8 + 5 + 9 + 12 = 41.
Given the number n used to create a password, write a program that computes the password f(n). Because n can be extremely large, it is given by its prime factorization.
Input
The first line contains the number of test cases T (T ≤ 500).
The first line of each test case contains C, the number of distinct prime factors of n (C ≤ 15).
Each of the next C lines contains a prime factor Pi and its exponent ai (2 ≤ Pi ≤ 1000, Pi is prime, 1 ≤ ai ≤ 50); that is, n = P1^a1 × P2^a2 × ⋯ × PC^aC. All primes given within a single test case are distinct.
Output
For each test case, print f(n) modulo 1,000,000,007 on its own line.