题目描述

使用火柴表示 $0$ 到$9$ 的方法如下：

给定一个整数 $n$，恰好用完 $n$ 根火柴可以组成多少个不同的正整数？注意正整数的首位不能为 $0$。输出方案数模 $1,000,000,007$ 的余数。

输入格式

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

输出格式

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

4

2

样例解释 1

四根火柴可以表示11或者4，所以有两种

6

6

样例解释 2

可行的方案是111，14，41，6，9，77

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2,000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 2,000,000$。