新年即将来临！为了庆祝，Matvey 决定给自己买一棵圣诞树。他去了一家出售图论树的商店。然而，当他到达时，由于选择太多，他无法做出决定。于是他决定计算一下高度为 $n$ 的圣诞树有多少种。

Matvey 认为一棵以顶点 1 为根的树是高度为 $n$ 的圣诞树，如果它满足以下条件：

• 假设根节点在第 1 层，其子节点在第 2 层，以此类推，第 $i$ 层顶点的子节点在第 $(i+1)$ 层。那么第 $i$ 层必须恰好有 $i$ 个顶点；
• 每个顶点最多有两个子节点；
• 按层从上到下对顶点进行编号，从 1 开始。在同一层内，从左到右对顶点进行编号。之后，考虑两个位于同一层且 $u < v$ 的顶点 $u$ 和 $v$，那么顶点 $u$ 的所有子节点（如果有的话）的编号必须小于顶点 $v$ 的所有子节点的编号。

Matvey 认为，如果存在两个数字 $i, j$，使得一棵树在顶点 $i$ 和 $j$ 之间有边，而另一棵树没有，则这两棵圣诞树是不同的。

对于高度为 3 的情况，有两种不同的圣诞树，如下图所示：

你需要计算高度为 $n$ 的不同圣诞树的数量。

输入格式

第一行包含一个数字 $n$ —— 圣诞树的深度 ($1 \le n \le 5000$)。

输出格式

输出一行一个数字 —— 深度为 $n$ 的圣诞树的数量。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3

样例输出 1

2

样例输入 2

4

样例输出 2

12