#include<bits/stdc++.h> using namespace std; int a[10001],g[10001]; int main() { int x; cin>>x; a[1]=1; a[2]=2; g[1]=0; g[2]=1; for(int i=3;i<=x;i++) { a[i]=(a[i-1]+a[i-2]*2+g[i-1])%10000; g[i]=(g[i-1]+a[i-2]*2)%10000; } cout<<a[x]; }