NUMTRYE - Number Theory (Easy)
f(n) and g(n) are two functions defined as following :
f(n) = ∏( pi2ei+1+1 ), where pi is prime factor of n and ei is highest power of pi in n.
g(n) = Σ( n/gcd(n,i) ); 1 <= i <= n
For a given value of n, you have to compute f(n)/g(n) % 1000000007.
Input
First line has T ( <= 10000 ), next T lines has 2 <= n <= 10^12.
Output
f(n)/g(n) % 1000000007 for each test case.
Example
Input: 2
2
4 Output:
3
3
Added by: | XeRoN!X |
Date: | 2012-03-25 |
Time limit: | 1s-13.48s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |