这里分了两种情况来分析，也就是y总说的只考虑最后的一步，也就是状态转移方程，这里分析的十分牛，ORZ

//分两种情况：第N列是排好的，没有伸到第N-1列；第N列是排好的，有一个排到了第N-1列的位置
//f[n] = f[n-1]+f[n-2]  第一种情况的方案数
//g[n-2] = f[n-3]+ g[n-3]  第二种情况的方案数
//f[N]是记录已经是排满了的方案数
//g[N]是记录有一个伸出来的方案数
#include<iostream>
using namespace std;
const int N = 1e6+10,mod = 10000;
int n;
int f[N];
int g[N];
int main(){
    cin>>n;
    f[0] = 1;//没有方案数
    g[1] = 1;//从一开始
    f[1] = 1;//只有竖着的
    for(int i=2;i<=n;i++)//从一开始的for,dp   nb
    {
        f[i]=((f[i-1]+f[i-2])%mod+2*g[i-2]%mod)%mod;
        g[i]=(g[i-1]+f[i-1])%mod;
    }
    cout<<f[n];
    return 0;
}