# Problem D

Exponentially Fun Problem

In your spare time, you’ve been at ETA building a machine with a
function $S(X) = N$ that
given a number $X$ outputs
a number $N$, where
$N$ is the sum of the
prime factors of $X$
counted with multiplicity. For example, $S(12) = S(2 \cdot 2 \cdot 3) = 2 + 2 + 3 =
7$. Your friend Mateusz wants to try your new machine.
He gave the machine a number $X$ but you now only see the number
$N$ on the display of the
machine. What is the *smallest* and
*biggest* number $X$ that Mateusz could have given your
machine, modulo $10^9 +
7$?

## Input

Input consists of only one integer $2 \le N \le 30000$.

## Output

Output two space-separated integers, the smallest possible $X$ that Mateusz could have given your machine, and the biggest possible $X$, modulo $10^9 + 7$.

Sample Input 1 | Sample Output 1 |
---|---|

7 |
7 12 |