Save The Land

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <complex>
#include <utility>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>

using namespace std;


typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef pair<int,int> PII;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rev(i,n) REV(i,n,0)
#define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define GI ({ int x; scanf("%d",&x); x; })
#define GLL ({ LL x; scanf("%lld",&x); x; })
#define ALL(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
#define PQ priority_queue
#define inf (int)(1e9)
#define linf (LL)(1e18)
#define eps (double)(1e-9)
#define leps (LD)(1e-18)
#define PI (double)(3.141592653589793238)
#define MOD 1000000007


void mult(LL a[4][4],LL b[4][4])
{
    LL c[4][4];
    rep(i,4)
        rep(j,4)
        {
            c[i][j]=0LL;
            rep(k,4)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
        }
    rep(i,4)
        rep(j,4)
            a[i][j]=c[i][j];
}

LL solve(LL a[4][4],LL b)
{
    b-=3;
    LL ans[4][4]={{1LL,0LL,0LL,0LL},{0LL,1LL,0LL,0LL},{0LL,0LL,1LL,0LL},{0LL,0LL,0LL,1LL}};
    while(b)
    {
        if(b&1)
            mult(ans,a);
        b>>=1;
        mult(a,a);
    }
    return (3*(ans[0][0]+ans[2][0]+3*ans[3][0])+(ans[0][1]+ans[2][1]+3*ans[3][1])+2*(ans[0][3]+ans[2][3]+3*ans[3][3]))%MOD;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    LL n;
    cin>>n;
    LL a[4][4]={{0LL,2LL,1LL,3LL},{1LL,0LL,0LL,0LL},{0LL,1LL,0LL,0LL},{0LL,0LL,0LL,2LL}};
    cout<<solve(a,n-1)<<'\n';
    return 0;
}