#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const ll mod=1e4;
ll n;
ll f[1000010][3];
signed main(){
   n=read();
	f[1][0]=1;
	f[2][0]=2;
	f[2][1]=1;
	f[2][2]=1;
	for (int i=3;i<=n;i++){
		f[i][0]=f[i-1][1]+f[i-1][2]+f[i-1][0]+f[i-2][0];
		f[i][1]=f[i-1][2]+f[i-2][0];
		f[i][2]=f[i-1][1]+f[i-2][0];
		f[i][0]%=mod;
		f[i][1]%=mod;
		f[i][2]%=mod;
	}
	printf("%lld",f[n][0]);
}