Given the number *n*, find the smallest positive integer which has exactly *n* divisors. It is guaranteed that for the given *n* the answer will not exceed 10<sup class="upper-index">18</sup>.
The first line of the input contains integer *n* (1 ≤ *n* ≤ 1000).
import math 
def POW(x, n):
    if n == 0:
        return 1
    if n % 2:
        return POW(x, n - 1) * x
    res = POW(x, n / 2)
    return res * res;

def rec(n, k):
    ans = POW(p[k], n - 1);
    for i in range(2, n + 1):
        if n % i == 0:
            ans = min(ans, rec(n // i, k + 1) * POW(p[k], i - 1))
    return ans
p = []
n = int(input())
for i in range(2, 1001):
    k = int(math.sqrt(i))
    for j in range(2, k + 1):
        if i % j == 0:
            break
    else:
        p.append(i)
print(rec(n, 0))



