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 |
