#include<iostream> using namespace std; long long f[1919810]; int main() { int n; cin>>n; f[1]=1;f[2]=2;f[3]=5; for(int i=4;i<=n;i++) f[i]=f[i-1]*2+f[i-3]; cout<<f[n]%10000; return 0; }