题目描述

我们定义$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}$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。