Smallest Integer with Given Prime Factor Permutation Count

The fundamental theorem of arithmetic states that every integer greater than \(1\) can be uniquely represented as a product of one or more primes. However, the ordering of these prime factors can vary.

For example:

• \(10 = 2 \times 5 = 5 \times 2\)
• \(20 = 2 \times 2 \times 5 = 2 \times 5 \times 2 = 5 \times 2 \times 2\)

Let \(f(k)\) be the number of different arrangements of the prime factors of \(k\). In the examples above, \(f(10)=2\) and \(f(20)=3\). In general, if the prime factorization of \(k\) is given by \[ k= p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, \] then the number of arrangements is \[ f(k)=\frac{(e_1+e_2+\cdots+e_r)!}{e_1!\,e_2!\cdots e_r!}. \]

Given a positive integer \(n\), your task is to determine the smallest integer \(k\) such that \(f(k)=n\). To minimize \(k\), note that assigning larger exponents to smaller primes (i.e. 2, 3, 5, ...) will yield a smaller product.

inputFormat

The input consists of a single positive integer \(n\), representing the desired number of distinct prime factor arrangements.

outputFormat

Output the smallest integer \(k\) for which \(f(k)=n\).

sample

1

2