**我自己想的是任何墙的长度都可以分成

剩一个空间的时候+。。。。+剩4个空间的时候

我觉得这样应该所有情况都有了，也没有理解题解的前缀和**

#include <iostream>
using namespace std;
int n,dp[1000005];
const int mod=10000;
int main(){
	cin>>n;
	dp[0]=1,dp[1]=1,dp[2]=2,dp[3]=5,dp[4]=11;
	for(int i=5;i<=n;i++){
		dp[i]+=dp[i-1]+dp[i-2]+dp[i-3]*2+dp[i-4]*2;
		dp[i]%=mod;
	}
	cout<<dp[n]<<endl;
	return 0;
}