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:

5

Output:

14