super-functions

View Russian Translation

For two integers a and b, integer d is their common divisors if and only if d divides both a and b. For example, 9 is a common divisor of 18 and 27, while 6 is not.

Among all common divisors of two integers a, b there always exists the largest one. Such a divisor is call the greatest common divisor, often denoted as gcd(a, b), and it is one of the most fundamental concepts in number theory.

This problem focuses on gcd function.

For a given integer Q the task is to answer Q queries, each one defined by a single integer n:
superpowers(n) := \sum\limits_{i=1}^n n^i \cdot gcd(i, n)
superexps(n) := \sum\limits_{i=1}^n 2^{n + i} \cdot gcd(i, n)
superphis(n) := \sum\limits_{i=1}^n \varphi(n^i) \cdot gcd(i, n)

where \varphi(m) is called Euler’s totient function and it counts the positive integers j ≤q m, for which gcd(m, j) = 1. For example, \varphi(4) = 2, because there are two integers not greater than 4, for which their greatest common divisor with 4 is 1, these numbers are 1 and 3.

Since all the above values can be very large, the goal is to compute their values modulo 10^9+7.

Input format:

In the first line there is a single integer Q denoting the number of queries. In each of the following Q lines there are two integers t and n, where t is either 1, 2 or 3 and denotes the type of the query, and n denotes the parameter of the query.

Output format:

Output exactly Q lines. In the i^{th} of them output the answer to the i^{th} query computed modulo 10^9+7.

Constraints:

1 ≤q Q ≤q 10^5
1 ≤q N ≤q 10^5

SAMPLE INPUT
3
1 4
2 4
3 4

SAMPLE OUTPUT
1124
1312
562

Explanation

There are 3 test cases to handle:

For the first query, superpowers(4), the answer is equal to:

4^1 \cdot gcd(1, 4) + 4^2 \cdot gcd(2, 4) + 4^3 \cdot gcd(3, 4) + 4^4 \cdot gcd(4, 4) = 1124

For the second query, superexps(4), the answer is equal to:

2^{4 + 1} \cdot gcd(1, 4) + 2^{4 + 2} \cdot gcd(2, 4) + 2^{4 + 3} \cdot gcd(3, 4) + 2^{4 + 4} \cdot gcd(4, 4) = 1312

For the third query, superphis(4), the answer is equal to:

\varphi(4^1) \cdot gcd(1, 4) + \varphi(4^2) \cdot gcd(2, 4) + \varphi(4^3) \cdot gcd(3, 4) + \varphi(4^4) \cdot gcd(4, 4) = 562

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Mathematics


Solutions: