Sam数

题目描述

小 Z 最近发现了一种非常有趣的数,他将这种数称之为 Sam 数。Sam 数具有以下特征:相邻两位的数字之差不超过 $2$。小 Z 还将 Sam 数按位数进行了分类,他将一个 $k$ 位 Sam 数称之为 $k$ 阶 Sam 数。但不幸的是小 Z 发现他数不清第 $k$ 阶的 Sam 数一共有多少个,这个时候机智的他想到了向你求助。

输入输出格式

输入格式


输入共一行一个整数 $k$,含义见题面。

输出格式


一行一个整数 $ans$,表示 $k$ 阶的 Sam 数的个数。 由于第 $k$ 阶 Sam 数非常多,你只需要输出 $ans\bmod 1000000007$。

输入输出样例

输入样例 #1

4

输出样例 #1

867

说明

**【数据规模和约定】** 对于 $30\%$ 的数据,$1\le k\le10^6$。 对于 $60\%$ 的数据,$1\le k\le 10^{12}$。 对于 $100\%$ 的数据,$1\le k\le10^{18}$。