Migrated from Lutece 1174 四句话题意

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Can you calculate $lcm(\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n})$.

$lcm$ is the least common multiple.

$\binom{n}{i}=\frac{n!}{i!(n-i)!}$.

This is the fourth sentence.

Input

There is only one integer $n(2\leq n\leq 1000000)$ in the first line.

Output

Output the $ans$ mod 1000000007.

Samples

2

2

Resources

2015 UESTC ACM Training for Math