普及模拟赛 6 - D

题目背景

小D所在的高中吃饭需要排队，学习成绩强的同学会得到大家的支持，拥有更高的声望值，但是不合适的排队的顺序会让同学们产生怨气。

又要排队吃饭了，小D的班级中一共有 $n$ 个同学，学校按照学习成绩给每个同学分配了一个声望值，所有同学的声望值构成了一个 $n$ 的排列。

大家都喜欢声望值高的同学，所以大家都希望声望值高的同学排在前面。

有些排队的方式会使得有些同学产生怨气，引起暴动。如果一个队列的最长上升子序列长度 $>2$ ，就会引起同学的暴动。

小D是班级的班长，因此他不希望排队的方式会导致产生扰乱纪律的同学，他想要知道有多少种合法的排队的方式，能够使得不存在扰乱纪律的同学。

一种 合法的排队方式 指的是，整个队列的最长上升子序列长度 $\le2$ 。

求 合法的排队方式 的数量。

输入共 $1$ 行，一个数字 $n$ 表示班级中同学的数量。

输出共 $1$ 行，表示合法的排队顺序的数量，答案对 $10000007$ 取模。

对于 $10\%$ 的数据，保证 $1 \le n \le10$ 。另有 $30\%$ 的数据，保证 $1\le n \le500$ 。对于所有数据，保证 $1\le n \le5000$ 。