NUMTRY  Number Theory
f(n) and g(n) are two functions defined as following :
f(n) = ∏( p_{i}^{2ei+1}+1 ), where p_{i} is prime factor of n and e_{i} is highest power of p_{i} 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
Warning: Test cases aren't random. Test files consist of large primes, strong pseudo primes, Carmichael numbers, squares of primes, product of large primes, worst possible test cases for fermat, miller rabin and other primality testing algorithms.
Note: You may try the tutorial version ( same test files, 5s100s time limit ).
hide comments
Yashpal:
20141231 19:55:28
Awesome Problem !! Reduced in Simple formula ! :) Last edit: 20141231 20:16:47 

Viplov Jain:
20140622 15:29:09
@xeronix please provide information on test files like given on this page >http://www.spoj.com/problems/APS2/


[Lakshman]:
20140607 13:47:00
Finally accepted took three moths to solve this problem.


[Lakshman]:
20140607 13:47:00
@XeRo!NiX My new Solution seems faster than 2 accepted users in easy version but here TLE, Do the easy version have different input files?


[Lakshman]:
20140607 13:47:00
@XeRo!NiX can you please suggest me some optimistion Last edit: 20140225 08:36:21 

apia:
20140607 13:47:00
It seems my total time is faster than Damian Straszak,but I got TLE again.


teoy:
20140607 13:47:00
the time limit is for one case or all cases ? 

Damian Straszak:
20140607 13:47:00
the tutorial version is very helpful, thank you 

Damian Straszak:
20140607 13:47:00
Ok, so this is tough. I Have no idea how to speed up my code. Any hints :)? 

Damian Straszak:
20140607 13:47:00
It's pretty hard to factorize n, when the time limit is so strict... (btw. why not equal limits for all testcases?).

Added by:  XeRoN!X 
Date:  20120323 
Time limit:  0.100s1.192s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Number Theory 