#include <iostream>
using namespace std;
const int MOD = 55555;
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 1 % MOD << endl;
        return 0;
    } else if (n == 1) {
        cout << 2 % MOD << endl;
        return 0;
    } else if (n == 2) {
        cout << 4 % MOD << endl;
        return 0;
    }
    int a = 1; 
    int b = 2;
    int c = 4; 
    int res;
    
    for (int i = 3; i <= n; ++i) {
        res = (a + b + c) % MOD;
        a = b;
        b = c;
        c = res;
    }
    
    cout << res << endl;
    return 0;
}
/**************************************************************
	Problem: 1689
	User: panyuchen
	Language: C++
	Result: Accepted
	Time:8 ms
	Memory:2072 kb
****************************************************************/