火柴数字

题目描述

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

给定一个整数 $n$，恰好用完 $n$ 根火柴可以组成多少个不同的正整数？

注意正整数的首位不能为 $0$。输出方案数模 $1{,}000{,}000{,}007$ 的余数。

输入格式

单个整数：表示 $n$。

输出格式

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

数据范围

对于 30% 的数据，$1 \le n \le 20$； 对于 60% 的数据，$1 \le n \le 2000$； 对于 100% 的数据，$1 \le n \le 2{,}000{,}000$。

样例输入 #1

4

样例输出 #1

2

说明：四根火柴可以表示 $11$ 或者 $4$，所以有两种。

样例输入 #2

6

样例输出 #2

6

说明：可行的方案是 $111, 14, 41, 6, 9, 7$。

知识点与难度

本题涉及的知识点从属于 GESP六级（动态规划、完全背包），难度等级：⭐⭐⭐。

测试点分布