**Time limit:**1.00 s**Memory limit:**512 MB

*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:

`5`

Output:

`14`