小 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。

对于 $30\%$ 的数据，$1 ≤ k ≤ 6$。
对于 $60\%$ 的数据，$1 ≤ k ≤ 1,000$。
对于 $100\%$ 的数据，$1 ≤ k ≤ 1,000,000$。