FORCE-T0166E: Tetrahedron

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

const int N = 1e7;
const int logN = log2(N);
const int MD = 1e9 + 7;

vvi bl[logN];

vvi matMultiply(vvi a, vvi b){
    int l = a.size();
    int m = a[0].size();
    int r = b[0].size();
    vvi ans(l, vi(r, 0));
    for(int i = 0; i < l; ++i){
        for(int j = 0; j < r; ++j){
            for(int k = 0; k < m; ++k){
                ans[i][j] = (ans[i][j] + (lli)a[i][k] * b[k][j]) % MD;
            }
        }
    }
    return ans;
}

int main(){

    int x;
    scanf("%d", &x);
    bl[0] = {{0, 1}, {3, 2}};
    for(int i = 1; i <= logN; ++i){
        bl[i] = matMultiply(bl[i - 1], bl[i - 1]);
    }
    vvi ans = {{1}, {0}};
    for(int i = logN; i >= 0; --i){
        if(x >= (1 << i)){
            ans = matMultiply(bl[i], ans);
            x -= (1 << i);
        }
    }
    cout << ans[0][0];

    return 0;
}