IARCS Tiling

/*
    Mode 0 - Complete width tiled.
    Mode 1 - Width 0-1 tiled.
    Mode 2 - Width 1-2 tiled.
    Mode 3 - Completely untiled.
*/
#include <iostream>
#include <cstring>
#define mod 10000
using namespace std;
int dp[1000000][4];
int main()
{
        int n;
        cin>>n;
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 1;
        dp[0][1] = dp[0][2] = 0;
        dp[0][3] = 1;
        for (int col = 1; col < n; col++)
        {
                for (int mode = 0; mode < 4; mode++)
                {
                        dp[col][mode] = 0;
                        if (mode == 0)
                        {
                                dp[col][mode] += dp[col-1][1];
                                dp[col][mode] += dp[col-1][2];
                                dp[col][mode] += dp[col-1][3];
                                dp[col][mode] += dp[col-1][0];
                                dp[col][mode] %= mod;
                        }
                        else if (mode == 1)
                        {
                                dp[col][mode] += dp[col-1][3];
                                dp[col][mode] += dp[col-1][2];
                                dp[col][mode] %= mod;
                        }
                        else if (mode == 2)
                        {
                                dp[col][mode] += dp[col-1][3];
                                dp[col][mode] += dp[col-1][1];
                                dp[col][mode] %= mod;
                        }
                        else if (mode == 3)
                        {
                                dp[col][mode] += dp[col-1][0];
                                dp[col][mode] %= mod;
                        }
                        else;
                }
        }
        int ans = dp[n-1][0];
        cout<<ans<<"\n";
}