题目描述

FJ 给了贝蒂一个数列，数列满足下面的性质：

\(1.\) 数列中的所有数都是不大于 \(n\) 的正整数；

\(2.\) 数列中至少有两个数。

\(3.\) 数列中任意两个数都不相等；

\(4.\) 当数列中数字大于 \(2\) 个时，对数列中任何 \(3\) 个相邻的数 \(a,b,c\) 来说，如果 \(a>b\)，那么 \(c>a\)，如果 \(a<b\)，那么 \(c<a\)。

比如，当 \(n=3\) 时，有下面几个这样的序列：

1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2

一共有 \(8\) 种，现在给定 \(n\)，请你帮贝蒂求出满足上面要求的数列的个数。

格式

输入格式

输入一行一个整数 \(n\)。\(（2<=n<=1000）\)

输出格式

输出一行一个整数，表示满足要求的序列个数，答案可能很大，请对 \(100000007\) 取模。

样例1

样例输入1

5

样例输出1

52

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T3\)