题目描述

给定一个 $n$，表示存在 $n$ 个符号 $\alpha_1,\alpha_2,\cdots, \alpha_n$，如果用 $=$ 或 $<$ 将这些符号串联起来，一共有多少种方案？例如当 $n = 3$ 时，有 $13$ 种方案，分别为：

• $\alpha_1<\alpha_2<\alpha_3$，$\alpha_1<\alpha_3<\alpha_2$ ，
• $\alpha_2<\alpha_1<\alpha_3$ ，$\alpha_2<\alpha_3<\alpha_1$，
• $\alpha_3<\alpha_1<\alpha_2$ ，$\alpha_3<\alpha_2<\alpha_1$；
• $\alpha_1=\alpha_2<\alpha_3$，$\alpha_3<\alpha_1=\alpha_2$ ，
• $\alpha_1=\alpha_3<\alpha_2$ ，$\alpha_2<\alpha_1=\alpha_3$ ，
• $\alpha_2=\alpha_3<\alpha_1$，$\alpha_1<\alpha_2=\alpha_3$，
• $\alpha_1=\alpha_2=\alpha_3$。 对于更大的 $n$，答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

输入格式

单个整数：表示 $n$。

输出格式

单个整数：表示方案数模 $1,000,000,007$ 的余数。

3

13

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 12$；
• 对于 $60\%$ 的数据，$1\leq n\leq 100$；
• 对于 $100\%$ 的数据，$1\leq n\leq 2000$。