#include<bits/stdc++.h> #define MAX_N 1000001 using namespace std; int n,a[MAX_N]={1,1,2},b[MAX_N]={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; }