数列

【题目描述】

我们定义$n-$数列是具有如下性质的数列。 数列的长度不小于$3$，且数列中的每个元素都是$1$到$n$之间的整数。 若数列为$a_1，a_2，…，a_m$，则对于任意$3≤k≤m$,都满足$(a_k-a_{k-2})(a_{k-1}-a_{k-2}) < 0$ 现在给你$n$，求$n-$数列的个数。答案对$10^9+7$取模。

【输入】

输入共一行为$n$。

【输出】

输出一行，表示$n-$数列的个数对$10^9+7$取模后的结果。

【输入样例】

3

【输出样例】

2

【提示】

【样例1说明】 两个$n-$序列分别是$(2,1,3)$和$(2,3,1)$。 【样例输入2】

666

【样例输出2】

805846404

【数据规模】 对于10%的数据，$n≤10$。 对于30%的数据，$n≤200$。 对于50%的数据，$n≤2000$。 对于70%的数据，$n≤10^{18}$。 对于100%的数据，$3≤n≤10^{5000}$。

666

805846404