- Time limit: 1.00 s
- Memory limit: 512 MB
For example, if $n=7$, there are four solutions:
- $\{1,3,4,6\}$ and $\{2,5,7\}$
- $\{1,2,5,6\}$ and $\{3,4,7\}$
- $\{1,2,4,7\}$ and $\{3,5,6\}$
- $\{1,6,7\}$ and $\{2,3,4,5\}$
The only input line contains an integer $n$.
Output
Print the answer modulo $10^9+7$.
Constraints
- $1 \le n \le 500$
Input:
7
Output:
4