#include<bits/stdc++.h> using namespace std; int main() { long long n,*f; cin>>n; f=new long long[n+1]; f[1]=1; for(int i=2;i<=n;i++) { if((i+1)%3==1) f[i]=f[i-1]*2+1; else if((i+1)%3==2) f[i]=f[i-1]*2-1; else f[i]=f[i-1]*2; f[i]%=10000; } // for(int i=1;i<=n;i++) cout<<i<<' '<<f[i]<<endl; cout<<f[n]; delete[] f; return 0; }