求满足如下条件的数字串个数：

• 长度为$n$。

• 每一位在$1$到$9$之间。

• 任意相邻两位的差的绝对值不超过$1$。

输出答案对$1000000007$取模的结果。

输入格式

第一行一个整数$n$。

输出格式

一个整数，表示答案。

样例输入

2

样例输出

25

数据规模

对于所有数据，保证$1\leq n\leq 10^5$。