题目描述

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

给定一个参数 n，请用 n 根火柴（必须全部用完），可以组成多少个不同的正整数？注意两位数以上的自然数首位不能为 0。输出方案数模 1,000,000,007 的余数。

输入格式

单个正整数：表示 n。

输出格式

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

数据范围

对于 30% 的数据，1≤n≤20；

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

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

样例数据

输入:

4

输出:

2

说明:

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

输入:

10

输出:

59