题目描述

有一个 $n$ 的排列 $a$，满足 $a_1=1$ 且对于每个 $2\le i\le n$ 的 $i$ 有 $|a_i-a_{i-1}|\le2$。现在给出 $n$，求一共有多少种可能的排列。

由于输出可能过大，答案对 $10^9+7$ 取模。

输入格式

输入共一行，一个整数 $n$。

输出格式

输出可能的排列数量。

样例 #1

样例输入 #1

4

样例输出 #1

4

样例 #2

样例输入 #2

32132

样例输出 #2

876675871

提示

样例解释 1

排列为 $(1,2,3,4),(1,2,4,3),(1,3,2,4),(1,3,4,2)$。

数据范围

对于 $100\%$ 的数据，$1\le n\le 10^{18}$。