/*
解题思路：
这题要数的是：n 个连续格子里，每个格子可以选择“放炸弹”或者“不放炸弹”，但是不能出现连续 3 个格子都放炸弹。
设 zd(g) 表示：前 g 个格子一共有多少种合法的炸弹安放方案。
先看小情况：
zd(1) = 2，因为 1 个格子可以不放，也可以放。
zd(2) = 4，因为 2 个格子有 00、01、10、11，都合法。
zd(3) = 7，因为 3 个格子本来有 8 种，但是 111 不合法，所以剩下 7 种。
接下来思考 g 个格子的情况。
因为不能连续放 3 个炸弹，所以一个合法方案的最后一段只能是：
1. 结尾是 0：最后一个格子不放炸弹，前 g - 1 个格子随便合法，所以有 zd(g - 1) 种。
2. 结尾是 10：最后两个格子是“放、不放”，前 g - 2 个格子随便合法，所以有 zd(g - 2) 种。
3. 结尾是 110：最后三个格子是“放、放、不放”，前 g - 3 个格子随便合法，所以有 zd(g - 3) 种。
为什么只看这三种？
因为合法方案里，连续炸弹最多只能有 2 个，所以结尾只能是 0、10、110，不能是 111。
因此递归关系是：
zd(g) = zd(g - 1) + zd(g - 2) + zd(g - 3)
但是普通递归会重复计算很多次，n 最大到 1000，会超时。
所以我们用“记忆化递归”：每个 zd(g) 算完后存到 f[g] 里，下次再遇到就直接返回。
另外答案很大，所以每次相加后都要 % 55555，不能最后才取模。
*/
#include <bits/stdc++.h> // #686. 【递归入门】炸弹安放
using namespace std;
const int MOD = 55555;
long long f[1005]; // 基本数组，f[g] 表示 g 个格子的合法方案数，-1 表示还没算过
long long zd(int g) { // 计算 g 个格子的炸弹安放方案数
    if (g == 0) return 1; // 0 个格子：什么都不放，也算 1 种空方案
    if (g == 1) return 2; // 1 个格子：不放、放
    if (g == 2) return 4; // 2 个格子：00、01、10、11
    f[g] = (zd(g - 1) + zd(g - 2) + zd(g - 3)) % MOD; // 结尾分别是 0、10、110
    return f[g];
}
int main() {
    int n;
    cin >> n;
    cout << zd(n);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long bom(long long n){
	if(n==1){
		return 2;
	}
	if(n==2){
		return 4;
	}
	if(n==3){
		return 7;
	}
	return bom(n-1)+bom(n-2)+bom(n-3);
}
int main(){
	
	long long n;
	cin>>n;
	cout<<bom(n)%55555;
	
	return 0;
	
}