HKE's Mysterious Function

HKE discovered an interesting function defined as follows. The function \(f(n)\) is defined by:

\(f(2)=1\). For any integer \(n\ge 3\), let \(t\) be the smallest positive integer such that \(n\) is not divisible by \(t\) (i.e. \(t\) is the smallest positive integer for which \(n\mod t\ne 0\)). Then, \(f(n)=f(t)+1\).

For example, consider \(n=6\):
    - 6 is divisible by 2 and 3, but not by 4, so \(t=4\).
    - Then, \(f(6)=f(4)+1\).
For \(n=4\):
    - 4 is divisible by 2 but not by 3, so \(t=3\) and \(f(4)=f(3)+1\).
For \(n=3\):
    - 3 is not divisible by 2, so \(t=2\) and \(f(3)=f(2)+1=2\).
Thus, \(f(4)=2+1=3\) and \(f(6)=3+1=4\>.

Your task is to compute the product:

\[ P(n)=f(2)\times f(3)\times \cdots \times f(n) \pmod{10^9+7} \]

Given an integer \(n\) (with \(n\ge 2\)), output the value of \(P(n)\).

inputFormat

The input consists of a single integer \(n\) (\(n\ge 2\)).

outputFormat

Output the value of \(P(n)=f(2)\times f(3)\times \cdots \times f(n)\) modulo \(10^9+7\).

sample

2

1