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 \leq 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 \leq Q \leq 10^5\)
\(1 \leq N \leq 10^5\)