#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int f[N]={0,1,2,5};
int main()
{
    int n;
    cin>>n;
    for(int i=4;i<=n;i++)
        f[i]=(2*f[i-1]%10000+f[i-3]%10000)%10000;
    cout<<f[n]<< endl;
    return 0;
}