The Preliminary Contest for ICPC China Nanchang National Invitational H题 Coloring Game

David has a white board with 2×N grids.He decides to paint some grids black with his brush.He always starts at the top left corner and ends at the bottom right corner, where grids should be black ultimately.

Each time he can move his brush up(↑), down(↓), left(←), right(→), left up(↖), left down(↙), right up(↗), right down (↘) to the next grid.

For a grid visited before,the color is still black. Otherwise it changes from white to black.

David wants you to compute the number of different color schemes for a given board. Two color schemes are considered different if and only if the color of at least one corresponding position is different.

Input

One line including an integer n(0<n ≤ 10^9)

Output

One line including an integer, which represent the answer mod 1000000007

题意：从左上角到右下角的染色方法（八个方向进行染色）往返是没有意义的。
dp打表找规律
1 = 1
2 = 4
3 = 12
4 = 26
a[n] = a[n - 1] * 3 (n > 1)
a[1] = 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans % mod;
}
int main() {
  long long n;
  cin  >> n;
  if (n == 1) {
    cout << "1" << endl;
    return 0;
  }
  cout << 4 * qpow(3, n - 2) % mod<< endl;
  return 0;
}