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\ast {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