#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;
#include"iostream"
using namespace std;
struct Matrix
{
    int n;
    LL a[3][3];
    Matrix (int n):n(n)
    {
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)a[i][j]=0;
    }

};
Matrix operator*(Matrix A,Matrix B)
{
    int n=A.n;
    Matrix res(n);
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    for(int k=0;k<n;k++)
    {
        res.a[i][j]+=(LL)A.a[i][k]*B.a[k][j]%MOD;
        res.a[i][j]%=MOD;
    }
    return res;
}
Matrix operator^(Matrix A,int b)
{
    int n=A.n;
    Matrix res(n),base=A;
    for(int i=0;i<n;i++)res.a[i][i]=1;
    while(b)
    {
        if(b&1)res=res*base;
        base=base*base;
        b>>=1;
    }
    return res;
}