【题目描述】

已知在1~N的序列P中，其LIS长度不超过2，询问可能的序列P的个数是多少。

【输入描述】

输入一个整数N。

【输出描述】

输出一个整数，表示答案 mod 1000000007的结果。

【样例输入】

1

【样例输出】

1

【数据范围及提示】

对于20%的数据，N ≤ 10；

对于40%的数据，N ≤ 20；

对于100%的数据，N ≤ 1000。