### 问题描述

七萤正在研究 $N$ 的排列。一个 $N$ 的排列是指 $1,2,...,N$ 这 $N$ 个正整数以某种顺序依次排列，总共有 $N!$ 种不同的排列。求满足以下条件的不同的排列个数。

假设排列中第 $i$ 个数字为 $p_i$，对所有 $i = 1,2,...,N$，都有 $|p_i - i| \leq 1$。

由于答案可能过大，你只需要输出答案对 $1000000007$ 取模后的值。

输入格式

一个正整数 $N$，含义如上所述。

输出格式

一个整数，表示满足条件的排列个数对 $1000000007$ 取模后的值。

样例输入

3

样例输出

3

说明

在样例中，满足条件排列如下：(1,2,3)，(2,1,3)，(1,3,2)。

评测数据规模

对于 $50$% 的评测数据，$1 \leq N\leq 10^{6}$。

对于 $100$% 的评测数据，$1 \leq N\leq 10^{18}$。