CSES - Permutations II

Time limit: 1.00 s
Memory limit: 512 MB

A permutation of integers $1,2,\ldots,n$ is called beautiful if there are no adjacent elements whose difference is $1$ .

Given $n$ , your task is to count the number of beautiful permutations.

Input

The only input line contains an integer $n$ .

Output

Print the number of beautiful permutations of $1,2,\ldots,n$ modulo $10^9+7$ .

Constraints

$1 \le n \le 1000$

Example

Input:

Output: