题目描述

小红定义一个排列是双生排列，当且仅当任意相邻两项之和均为奇数。现在小红想知道，长度为 $n$ 的双生排列共有多少种？由于答案可能过大，请对 ($10^9$^+7)取模。长度为 $n$ 的排列是由 $1$~n这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{$2$,$3$,$1$,$5$,$4$} 是一个长度为 $5$ 的排列；而 {$1$,$2$,$2$}（存在重复元素）和 {$1$,$3$,$4$}（包含超出范围的数）都不是排列。输入描述输入一个整数 $n$（$2<=n<=10$^$5$^），代表排列的长度。输出描述输出一个整数，代表长度为 $n$ 的双生排列数量对 ($10^9$^+7) 取模的答案。

输入格式

输入一个整数 $n$，代表排列的长度

输出格式

输出一个整数，代表最终答案

样例

样例输入 1

3

样例输出 1

2

提示

在这个样例中，长度为 $3$ 的排列有：{$1$，$2$，$3$}，{$1$，$3$，$2$}，{$2$，$1$，$3$}，{$2$，$3$，$1$}，{$3$，$1$，$2$}，{$3$，$2$，$1$}。其中{$1$,$2$,$3$}和{$3$，$2$，$1$}为双生排列。