DCEPC12G - G Force

no tags 

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 : indeed it's a good problem, but imho need harder constraints.
(Edit) Top psolvers are invited to set a new edition ; if they want.

Last edit: 2016-06-28 23:22:37
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