3137: 火柴数字（一）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
使用火柴表示 00 到99 的方法如下：
给定一个整数 �n，恰好用完 �n 根火柴可以组成多少个不同的正整数？注意正整数的首位不能为 00。输出方案数模 1,000,000,0071,000,000,007 的余数。
给定一个整数 �n，恰好用完 �n 根火柴可以组成多少个不同的正整数？注意正整数的首位不能为 00。输出方案数模 1,000,000,0071,000,000,007 的余数。
输入
- 单个整数：表示 �n。
- 对于 30%30% 的数据，1≤�≤201≤n≤20；
- 对于 60%60% 的数据，1≤�≤2,0001≤n≤2,000；
- 对于 100%100% 的数据，1≤�≤2,000,0001≤n≤2,000,000。
输出
- 单个整数：表示方案数模 1,000,000,0071,000,000,007 的余数。
样例输入 复制
4样例输出 复制
2提示
四根火柴可以表示11或者4，所以有两种
可行的方案是111，14，41，6，9，77
可行的方案是111，14，41，6，9，77