Cho số nguyên dương k, tìm số bé nhất \(x\) có đúng k ước số.

Do số quá lớn nên kết quả bài toán \(x\) cần được chia dư cho m với \(m=2*10^{18}+1\).

Đầu vào

Một dòng chứa số nguyên dương k.

Đầu ra

Một dòng duy nhất chứa kết quả bài toán.

Giới hạn

30%: \(2 \le k \le 32\)

40%: \(k \le 10^6\), Kết quả bài toán trước khi chia dư < m

30%: \(k \le 10^{12}\)

Ví dụ 1

Đầu vào

4

Đầu ra

6

Giải thích

6 là số bé nhất có đúng 4 ước số là 1, 2, 3, 6