题目描述

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

输入格式

第一行为一个整数 k，含义见题面。

输出格式

一行一个整数 ans，表示 k 阶的 Sam 数的个数。

由于第 k 阶 Sam 数非常多，你只需要输出 ans mod 1000000007。

4

867

提示

【数据规模和约定】

对于 30%的数据，1 ≤ k ≤ 10^6。

对于 60%的数据，1 ≤ k ≤ 10^12。

对于 100%的数据，1 ≤ k ≤ 10^18。