时间限制：1秒　　内存限制：256M

---

【题目描述】

　　如下图所示：数字 0 到 9，它们的火柴数量分别是：6、2、5、5、4、5、6、3、7、6。

　　现在给你 \(n\) 根火柴，问你能拼出多少个不同的整数？
　　 注意：拼出的整数不能有前导 0。

【输入格式】

　　输入数据包含多组数据，每组数据占一行一个整数 \(n\) ，表示火柴棍的数目。

【输出格式】

　　每组数据输出一行，表示对应输入的答案 \( mod\ 10^9+7\)。

【输入输出样例】

　Input

1
2
3
4
5
6
7
10
13
20

　Output

0
1
2
4
9
16
28
139
698
30261

【样例说明】

　　对于 \(n=4\) 时，可以拼成的整数有： 1，4 ，7，11。

【数据限制】

　　对于40%的数据满足：\(0<n≤40\)。
　　对于80%的数据满足：\(0<n≤2000\)，每个测试点最多不超过10组数据。
　　对于100%的数据满足：\(0<n≤2000\)，每个测试点最多不超过100组数据。

【来源】

　　Mr.he