添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+9;
#define int long long
int mod=1e9+7;
signed main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
        // dp[2][0]=3;
        // dp[2][1]=3;
        // dp[2][2]=3;
        // dp[2][3]=3;
        int dp=1,g=0;//走一步 dp等于1  在d的点为0

    //走n步 结束在j
    for(int i=2;i<=n;i++){
                int now=dp;//记录上一个状态
                dp=g+dp*2;//当前不是d的点为在d的点加上 其余下面两个点的转移
                dp%=mod;
                g=now*3%mod;//等于下面两个点的转移
            // }
       
    }
   cout<<g<<"\n";
    return 0;
}