問題文

縦 2 行、横 W 列のマス目があります。
どの隣接する 2 マスも同じ色にならないように、マス目を赤・黄・緑・青の 4 色で塗る方法は何通りありますか。

制約

• W は 1 以上 10^{18} 以下の整数

入力例 1

1

出力例 1

12

入力例 2

2

出力例 2

84

入力例 3

100

出力例 3

908287499