DCEPC12G - G Force
Prime(n) is defined as number of primes less than equal to n.
Totient(n) is defined as the number of positive integers less than or equal to n that are relatively prime to n.
F(n) = Prime(n) – Totient(n)
and we don’t like negative values, so if F(n) < 0, consider it as 0.
G(n) = Totient(n) ^ (Factorial (F(n)))
You are given a number n. You have to output G(n) % 10^9+7.
Input
First line consists of T, the number of test cases.
Each of the next T lines contains one integer n.
Output
Output T lines each line containing the value of function G(n) % 10^9+7
Constraints
1<=T<=100
1<=n<=10000000
Example
Input: 1 2 Output: 1
hide comments
Francky:
2016-06-28 14:30:24
N vs n ; fixed.
|
|
Piyush Kumar:
2016-06-28 10:05:47
This is a good number theory implementation easy problem :) ! Last edit: 2016-06-28 10:06:24 |
|
[Lakshman]:
2015-10-14 19:11:23
@sarvesh_19: can you please delete your comment. Please admin delete the below comment. Thanks |
|
I know nothing:
2014-10-16 15:35:28
thanks Lakshman for ur comment i got my silly mistake |
|
[Lakshman]:
2014-10-15 18:42:29
@I know nothing your output for 1,2,30 is correct after that all are incorrect(IDEONE output). |
|
[Lakshman]:
2014-10-15 18:21:06
@LeppyR64 Yes. |
|
LeppyR64:
2014-10-15 17:42:02
Is n the same as N? |
|
anurag garg:
2014-01-07 20:04:53
very good question dce coders.... |
Added by: | dce coders |
Date: | 2013-12-07 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC |