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

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\).