#6 「 小迟的数字2 」

统计

小迟喜欢上了一些数字。如果一个数字的十进制表示中,有连续的1个1,或者有连续的2个2,或者有连续的3个3,或者有连续的4个4,或者有连续的5个5,或者有连续的6个6,或者有连续的7个7,或者有连续的8个8,或者有连续的9个9,小迟会认为这个数字是good number。

现在小迟想数一数在所有$N$位数中有多少个good number?

这个数字可能有点大,所以对$10^9 + 7$ 取模就好了。

输入格式

输入数据第一行为$N$。

输出格式

一行一个整数,表示答案。

样例数据

input

3

output

269

数据规模与约定

$ 1 \le N < 10^3 $。

时间限制:1s

空间限制:512MB

Author: zrt