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 < 10¹⁴).  There are 100 inputs total.

Output

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

Example

Input: 
3
1024

Output: 
9
97947700