串联计数(Serial Counting)

题目描述

给定 $n$ 个变量 $\alpha_1,\alpha_2,\cdots,\alpha_n$，如果用 $=$ 或 $<$ 将这些变量串联起来，一共有多少种方案？例如 $n=3$ 时有 $13$ 种方案。答案对 $1,000,000,007$ 取模。

输入格式

• 单个整数：表示 $n$。

输出格式

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

样例输入 #1

3

样例输出 #1

13

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐。

测试点分布