题目描述 Description
已知1～N的排列P的LIS(最长上升子序列)不超过2，求可能的P的个数。答案取模10^9+7。
输入描述 Input Description
一行一个整数N。
输出描述 Output Description
输出一行一个整数，描述可能的排列P的个数mod1000000007的结果。
样例输入 Sample Input
1
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
测试点编号 数据范围
1,2 N≤10
3,4 N≤20
5,6,7,8,9,10 N≤1000