All submissions for this problem are available.
Hermione Granger, the most talented witch of her generation, likes to solve various types of mathematical problems in the Arithmancy class. Today, the professor has given her the following task:
Find the number of fractions a/b such that-
1. gcd(a, b) = 1
2. 0 < a/b < 1
3. a * b = (n!) ^ (n!)
Where "n!" denotes the factorial of n and "^" denotes power, i.e. (2!) ^ (2!) = 4.
She is quite confident that she can solve it for n <= 10,000,000 (i.e. 10^7), but then she remembers that she has to study some case history so that she can help Hagrid to win the case of Buckbeak. So, she wants your help to solve the problem.
There will be one line for each test case containing the number n (1 <= n <= 10,000,000). Input will be terminated by EOF. There will be around 20,000 test cases.
For each case, print the number of fractions in a separate line. This number may be very large, so print the answer modulo 10,007.
Input: 1 2 Output: 0 1
|Time Limit:||0.268 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.