#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
int f(int x,int y,int z){
  return 16*x+4*y+z;
}
int main() {
  int n,i,j,k,l,m,ans=0;
  cin>>n;
  vector<vector<int>> a(64,vector<int>(n+1));
  for(i=0;i<64;i++) a.at(i).at(3)=1;
  a.at(f(0,1,2)).at(3)=0;
  a.at(f(0,2,1)).at(3)=0;
  a.at(f(1,0,2)).at(3)=0;
  for(i=3;i<n;i++){
    for(j=0;j<4;j++){
      for(k=0;k<4;k++){
        for(l=0;l<4;l++){
          for(m=0;m<4;m++){
            if((j!=0||k!=1||m!=2)&&(j!=0||l!=1||m!=2)){
              a.at(f(k,l,m)).at(i+1)+=a.at(f(j,k,l)).at(i);
              a.at(f(k,l,m)).at(i+1)%=mod;
            }
          }
        }
      }
    }
    a.at(f(0,1,2)).at(i+1)=0;
    a.at(f(0,2,1)).at(i+1)=0;
    a.at(f(1,0,2)).at(i+1)=0;
  }
  for(i=0;i<64;i++) ans=(ans+a.at(i).at(n))%mod;
  cout<<ans<<endl;
}
### Prompt

Generate a CPP solution to the following problem:

You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

* The string does not contain characters other than `A`, `C`, `G` and `T`.
* The string does not contain `AGC` as a substring.
* The condition above cannot be violated by swapping two adjacent characters once.

Constraints

* 3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:


N


Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Examples

Input

3


Output

61


Input

4


Output

230


Input

100


Output

388130742

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
int f(int x,int y,int z){
  return 16*x+4*y+z;
}
int main() {
  int n,i,j,k,l,m,ans=0;
  cin>>n;
  vector<vector<int>> a(64,vector<int>(n+1));
  for(i=0;i<64;i++) a.at(i).at(3)=1;
  a.at(f(0,1,2)).at(3)=0;
  a.at(f(0,2,1)).at(3)=0;
  a.at(f(1,0,2)).at(3)=0;
  for(i=3;i<n;i++){
    for(j=0;j<4;j++){
      for(k=0;k<4;k++){
        for(l=0;l<4;l++){
          for(m=0;m<4;m++){
            if((j!=0||k!=1||m!=2)&&(j!=0||l!=1||m!=2)){
              a.at(f(k,l,m)).at(i+1)+=a.at(f(j,k,l)).at(i);
              a.at(f(k,l,m)).at(i+1)%=mod;
            }
          }
        }
      }
    }
    a.at(f(0,1,2)).at(i+1)=0;
    a.at(f(0,2,1)).at(i+1)=0;
    a.at(f(1,0,2)).at(i+1)=0;
  }
  for(i=0;i<64;i++) ans=(ans+a.at(i).at(n))%mod;
  cout<<ans<<endl;
}
```