Counting Permutations

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

5

Output

14