DCEPC604 - Unlock it ! Part 2

Now you all helped Vaibhav solve the puzzle and open the gate last time (although not too much help). But as soon as he opens the gate, there is another puzzle to open the front door. Let’s see whether this time you all are able to help him or not.

  • Fac(n) = number of trailing zeroes in n!
  • Fact(n) = Fac(n) % 25 + 1
  • F(0) = 1
  • F(1) = 1
  • F(2) = 1
  • F(n) = product of all odd primes less than or equal to n (for n <= 10)
  • F(n) = 4^fact(n) * f(n/5) * f(n/10) (for n > 10)

For every fraction, a floor value is taken for evaluation.

For eg. F(11)=4^fact(11) * F(floor(11/5)) * F(floor(11/10)) = 4^3 * F(2) * F(1) = 64

Given N, find the maximum value of (a^b) % mod such that a and b satisfies the relation gcd(a,b) = F(N). (Gcd : Greatest common divisor.)

Input

First line gives T, total number of test cases. Next T lines give the number N.

Output

For each test case, print the desired value on a new line.

Constraints

T <= 10

N <= 10^6

mod = 10^9

NOTE: a must be <= 5*F(n) and b must be <=5*F(n), a can be equal to b and mod=10^9

Example

Input:
1
2

Output:
1024

Added by:dce coders
Date:2012-04-22
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2023-03-17 04:53:39 Ishan
Time limit is strict .It's funny that I needed to do constant optimization in an O(1) solution to pass.
2015-03-11 03:06:41 Soma
@dce coder: can u tell me where my code fails. i am getiing WA. submission id=13759205;

Edit:
@author :please update the problem statement.
@everyone: Fac(n) = no of trailing zeroes in n!

Last edit: 2015-07-06 04:03:21
2013-06-29 10:33:15 Amit RC
you can't get AC by blindly following what happened in Unlock part 1...this one is slightly different, but only slightly!
2012-04-25 13:35:22 noju
getting WA please check my submission 6903877..i am getting AC for unlock part 1 with same approach.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.