DIVISER9 - Divisors VI

Find the smallest integer with exactly N odd divisors, where each divisor is greater or equal to 1 !!!

For example for 3 odd divisors, 9 (factors 1, 3, 9) is minimum.

Input

Each line contain N (0 < N < 1014).  There are 100 inputs total.

Output

One answer on each line for each N, Modulo 1000000007.

Example

Input: 
3
1024

Output:
9
97947700

Added by:Chen Xiaohong
Date:2010-10-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET

hide comments
2019-08-21 17:38:18
Dataset is too much weak!
2012-10-27 12:10:19 (Tjandra Satria Gunawan)(曾毅昆)
nice problem, similar to my problem INVDIV ;-)
2010-10-22 04:51:11 [Rampage] Blue.Mary
A problem used in recently UVa Regional Warmup Contest :-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.