111 podryad

#include <iostream>

using namespace std;

int main(){
    int n;
    cin>>n;

    if(n==1){
        cout<<3;
        return 0;
    }
    else if(n==2){
        cout<<9;
        return 0;
    }
    else if(n==3){
        cout<<26;
        return 0;
    }

    int x11=2;
    int xx1=6;
    int last=26;

    for(int i=4;i<=n;i++){
        int x11_1=xx1;
        int xx1_1=last-xx1-x11;
        int last_1=last*2+(last-x11);
        x11=x11_1;
        xx1=xx1_1;
        last=last_1;
    }
    cout<<last;
}