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.
The only input line contains an integer $n$ .
Print the number of beautiful permutations of $1,2,\ldots,n$ modulo $10^9+7$ .