2943: Sam数_大数据
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
小 x 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。Sam 数具 有以下特征： 相邻两位的数字之差不超过 2。 小 x 还将 Sam 数按位数进行了分类， 他将一个 k 位 Sam 数称之为 k 阶 Sam 数。但不幸的是，小 x 发现他数不清第 k 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。
输入
第一行为一个整数 k，含义见题面。
输出
输出一行一个整数 ans，表示 k 阶的 Sam 数的个数。 由于第 k 阶 Sam 数非常多，你只需要输出 ans mod 1,000,000,007。
样例输入 复制
4样例输出 复制
867提示
【数据规模和约定】
对于 30%的数据，1 ≤ k ≤ 10^6。 对于 60%的数据，1 ≤ k ≤ 10^12。 对于 100%的数据，1 ≤ k ≤ 10^18。