← 返回题目列表

AtCoder · tessoku_book_fh

C10. 长网格

中文机器翻译题面 查看原题

配点: 1000 点

問題文

縦 2 行、横 W 有一个列网格。
任意相邻的 2 方格也不能是相同的颜色,方格用红、黄、绿、蓝四色 4 涂色的方法有多少种?

制約

  • W 是 您也可以写 1 以上 10^{18} 的整数 给出了

入力

输入是按以下格式从标准输入给出的。

W

出力

答案 请打印除以 1000000007 除的余数。 用


入力例 1

1

出力例 1

12

入力例 2

2

出力例 2

84

入力例 3

100

出力例 3

908287499