Arrogant Zenyk

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka loves mathematics very much, especially problems involving prime numbers. This time she came up with an interesting function. For positive integers \(n > 1\), she defines the function \(f(n) = n + p(n)\), where \(p(n)\) is the smallest prime divisor of the number \(n\).

Zenyk just laughed when he saw this function. He thinks that children in the older kindergarten group can compute the value of \(f(n)\) for a given \(n\), and therefore it’s not even worth mentioning the function \(f\) at The Algo Battles.

Marichka wants to teach arrogant Zenyk a lesson and gave him the following problem.

Given a number \(n\). You need to find the smallest \(m\) such that the equation \(f(k) = m\) has at least \(n\) solutions, i.e., different values of \(k\) that satisfy the equality. Since the number \(m\) can be large, output the remainder of its division by the prime number \(10^9 + 7\).

Zenyk stopped laughing and is scratching the back of his head...

Input

The single line contains an integer \(n\).

Output

In a single line, output an integer \(m\) — the remainder of the answer divided by the prime number \(10^9 + 7\).

Constraints

\(1 \le n \le 10^5\).

Samples

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

Notes

The values of the function \(f\) for several positive integers: \(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\).

The equation \(f(k) = 6\) has two solutions: \(3\) and \(4\). For \(m < 6\), the equation \(f(k) = m\) has at most one solution. Therefore, for \(n=2\) the answer is \(m = 6\).