[HackerEarth] View Russian Translation - P18630

题目描述

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$

输入格式

见题面

输出格式

见题面

样例输入

样例输出

时间限制	2000 ms
内存限制	256 MB
难度	提高-
提交数	0
通过数	0
通过率	0.0%

P18630 [HackerEarth] View Russian Translation

题目描述

输入格式

输出格式

样例输入

样例输出