#MX109. 排队方式
排队方式
题目背景
小D所在的高中吃饭需要排队,学习成绩强的同学会得到大家的支持,拥有更高的声望值,但是不合适的排队的顺序会让同学们产生怨气。
题目描述
又要排队吃饭了,小D的班级中一共有 个同学,学校按照学习成绩给每个同学分配了一个声望值,所有同学的声望值构成了一个 的排列。
大家都喜欢声望值高的同学,所以大家都希望声望值高的同学排在前面。
有些排队的方式会使得有些同学产生怨气,引起暴动。如果一个队列的最长上升子序列长度 ,就会引起同学的暴动。
小D是班级的班长,因此他不希望排队的方式会导致产生扰乱纪律的同学,他想要知道有多少种合法的排队的方式,能够使得不存在扰乱纪律的同学。
一种 合法的排队方式 指的是,整个队列的最长上升子序列长度 。
求 合法的排队方式 的数量。
输入格式
输入共 行,一个数字 表示班级中同学的数量。
输出格式
输出共 行,表示合法的排队顺序的数量,答案对 取模。
样例 1 输入
3
样例 1 输出
5
样例 2 输入
18
样例 2 输出
7638371
样例 3 输入
500
样例 3 输出
7288045
数据规模与约定
对于 的数据,保证 。 另有 的数据,保证 。