版权声明

本题版权归 Long Long OJ 所有。

题目描述

有一个 $n$ 的排列 $a$，满足 $a_1=1$ 且对于每个 $2\le i\le n$ 的 $i$ 有 $|a_i-a_{i-1}|\le2$。

现在给出 $n$，求一共有多少种可能的排列。

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

输入格式

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

输出格式

输出可能的排列数量。

样例

4

4

32132

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}$。