该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】

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

【输入格式】

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

【输出格式】

一行一个整数ans，表示k阶的Sam数的个数。 由于第k阶Sam数非常多，你只需要输出ans mod 1,000,000,007。

【样例输入】

4

【样例输出】

867

【数据规模和约定】

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

对于60%的数据，1 ≤ k ≤ 1000。

对于100%的数据，1 ≤ k ≤ 1000000。