该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

使用火柴表示 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≤n≤20；

对于 60% 的数据，1≤n≤2,000；

对于 100% 的数据，1≤n≤2,000,000。