#include <iostream>

constexpr int MAX_N = 1000001, MOD = 10000;

/// dp[0][i]: 长方形；dp[1][i]: 阶梯型，i 为短边长
long long dp[2][MAX_N];

void init_dp() {
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[0][2] = 2;
    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[1][2] = 2;
    for (int i = 3; i < MAX_N; i++) {
        dp[0][i] = (dp[0][i - 1] + dp[0][i - 2] + dp[1][i - 2] * 2) % MOD;
        dp[1][i] = (dp[0][i - 1] + dp[1][i - 1]) % MOD;
    }
}

void log_dp(int n) {
    for (int i = 1; i <= n; i++) {
        std::clog << dp[0][i] << ' ';
    }
    std::clog << std::endl;
    for (int i = 1; i <= n; i++) {
        std::clog << dp[1][i] << ' ';
    }
    std::clog << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    init_dp();
    int n;
    std::cin >> n;
    std::cout << dp[0][n] % MOD << std::endl;;
    log_dp(n);

    return 0;
}