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