#MX109. 排队方式

排队方式

题目背景

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

题目描述

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

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

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

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

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

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

输入格式

输入共 11 行,一个数字 nn 表示班级中同学的数量。

输出格式

输出共 11 行,表示合法的排队顺序的数量,答案对 1000000710000007 取模。

样例 1 输入

3

样例 1 输出

5

样例 2 输入

18

样例 2 输出

7638371

样例 3 输入

500

样例 3 输出

7288045

数据规模与约定

对于 10%10\% 的数据,保证 1≤n≤101 \le n \le10。 另有 30%30\% 的数据,保证 1≤n≤5001\le n \le500。