bad problem

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

#define nl "\n"
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int) v.size()

template<typename T = int>
istream &operator>>(istream &in, vector<T> &v) {
    for (auto &x: v) in >> x;
    return in;
}

template<typename T = int>
ostream &operator<<(ostream &out, const vector<T> &v) {
    for (const T &x: v) out << x << " ";
    return out;
}

void Sira() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
int n;
const int N = 1e6 + 5;
int dp[N][4];
int rec(int sum , int one){
    // base case;
    if(one > 3) return 0;
    if(sum >= n) return sum == n and !one;

    // memo
    int & ret = dp[sum][one];
    if(~ret) return ret;

    // rec

    ret = 0;

    if(!one){
        ret += rec(sum + 2 , 2);
        ret += rec(sum + 1 , one + 1);
    }

    ret += rec(sum + 2 , 0);

    return ret;

}
void solve(){
    cin >> n;

    for(auto & i : dp){
        memset(i , -1 , sizeof i);
    }

    cout << rec(1 , 1) + rec(2 , 0) << nl;

}

int main() {
    Sira();
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}