#include <iostream> #define MAX_N 1000001 using namespace std; int n; int a[MAX_N] = {1,1,2}; int 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; }