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