DIVISER9 - Divisors VI

no tags 

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

hide comments
sjshohag: 2019-08-21 17:38:18

Dataset is too much weak!

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-27 12:10:19

nice problem, similar to my problem INVDIV ;-)

[Rampage] Blue.Mary: 2010-10-22 04:51:11

A problem used in recently UVa Regional Warmup Contest :-)


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