Зарозумілий Зеник

Limits: 2 sec., 256 MiB

Марічка дуже любить математику, особливо задачі на прості числа. Цього разу вона вигадала цікаву функцію. Для натуральних чисел $n > 1$ вона визначає функцію $f(n) = n + p(n)$, де $p(n)$ — це найменший простий дільник числа $n$.

Зеник побачивши цю функцію лише посміявся. Він думає, що обчислити значення $f(n)$ для заданого $n$ можуть і діти старшої групи дитсадка, а тому навіть не варто згадувати про функцію $f$ на The Algo Battles.

Марічка хоче провчити зарозумілого Зеника і дала йому таку задачу.

Задано число $n$. Потрібно знайти найменше $m$ таке, що рівняння $f(k) = m$ має хоча б $n$ розв’язків, тобто різних значень $k$, що задовольняють рівність. Оскільки число $m$ може бути великим, виведіть остачу від ділення його на просте число $10^9 + 7$.

Зеник перестав сміятися й чухає потилицю...

Input

В одному рядку задано ціле число $n$.

Output

В одному рядку виведіть ціле число $m$ — остачу від ділення відповіді на просте число $10^9 + 7$.

Constraints

$1 \le n \le 10^5$.

Samples

Input (stdin) сopy	Output (stdout) сopy
2	6

Notes

Значення функції $f$ для кількох натуральних чисел: $f(2) = 2 + 2 = 4$, $f(3) = 3 + 3 = 6$, $f(4) = 4 + 2 = 6$, $f(5) = 5 + 5 = 10$, $f(6) = 6 + 2 = 8$, $f(7) = 7 + 7 = 14$, $f(8) = 8 + 2 = 10$, $f(9) = 9 + 3 = 12$.

Рівняння $f(k) = 6$ має два розв’язки: $3$ і $4$. Для $m < 6$ рівняння $f(k) = m$ має не більше ніж один розв’язок. Тому для $n=2$ відповіддю є $m = 6$.