题解 | 小红的二叉树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

ll qpow(ll a,ll b,ll p)
{
    ll res =1;
    for(;b;b>>=1)
    {
        if(b&1)res = res*a%p;
        a = a*a%p;
    }
    return res;
}


int main()
{
    ll n;
    cin>>n;
    if(n==1)
    {
        cout<<0<<'\n';
    }
    else 
    {
        ll res = 1;
        ll cur = 1;
        for(int i=2;i<n;i++)
        {
            cur = cur*2%mod;
            res = (res+cur*3)%mod;
        }
        // cur = cur*2%mod;
        // res = (res+cur)%mod;
        cout<<res<<'\n';
    }

    

    return 0;
}