#P46. [KBC003E] Permutation

[KBC003E] Permutation

版权声明

本题版权归 Long Long OJ 所有。

题目描述

有一个 nn 的排列 aa,满足 a1=1a_1=1 且对于每个 2in2\le i\le niiaiai12|a_i-a_{i-1}|\le2

现在给出 nn,求一共有多少种可能的排列。

由于输出可能过大,答案对 109+710^9+7 取模。

输入格式

输入共一行,一个整数 nn

输出格式

输出可能的排列数量。

样例

4
4
32132
876675871

提示

样例 11 解释:

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


对于 100%100\% 的数据,1n10181\le n\le 10^{18}