#include<iostream>
using namespace std;
int a[100001],b[1000001];

int main()
{
	int n;
	cin>>n;
	a[0]=1;	//b[0]=0 递推边界 
	a[1]=b[1]=1;
	for(int i=2;i<=n;i++)
	{
		a[i]=((a[i-1]+a[i-2])%10000+2*b[i-2]%10000)%10000;
		
		b[i]=(b[i-1]+a[i-1])%10000;
	}
	cout<<a[n];
	
	return 0;
}