求满足如下条件的数字串个数:
长度为$n$。
每一位在$1$到$9$之间。
任意相邻两位的差的绝对值不超过$1$。
输出答案对$1000000007$取模的结果。
输入格式
第一行一个整数$n$。
输出格式
一个整数,表示答案。
样例输入
2
样例输出
25
数据规模
对于所有数据,保证$1\leq n\leq 10^5$。
求满足如下条件的数字串个数:
长度为$n$。
每一位在$1$到$9$之间。
任意相邻两位的差的绝对值不超过$1$。
输出答案对$1000000007$取模的结果。
第一行一个整数$n$。
一个整数,表示答案。
2
25
对于所有数据,保证$1\leq n\leq 10^5$。