#include"stdio.h"
int f[10000001];
int g[10000001];
int main() {
    int n;
    scanf("%d",&n);
    f[0]=f[1]=1;
    for(int i=2;i<=n;i++){
    f[i]=((f[i-1])%10000+(f[i-2])+(g[i-1])%10000)%10000;
    g[i]=((f[i-2]*2)%10000+(g[i-1])%10000)%10000;
    }
	printf("%d",f[n]);
	return 0;
}