#include<stdio.h>
using namespace std;
int main(){
	long long n;
	scanf("%d",&n);
	long long f[n+1],g[n+1];
	f[0]=1;
	f[1]=1;
	f[2]=2;
	f[3]=5;
	g[3]=1;//g代表当最后一个是L时的情况（未乘2），具体如下。 
	for(int i=4;i<=n;++i)
	{
		f[i]=f[i-1]+f[i-2]+2*g[i-1];
		/*公式推导：
		若令g[n-1]=f[n-3]+f[n-4]+...f[0];
		则g[n]=f[n-2]+g[n-1]-f[0];*/
		g[i]=f[i-2]+g[i-1]-1;
	}
	printf("%lld",f[n]%10000);
	return 0; 
}```
求各位大佬看看究竟哪有问题，想不懂。