友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
我们定义$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}$。