#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>

#define pb push_back
#define ff first
#define ss second
#define sqr(x) (x) * (x)
#define cb(x) (x) * (x) * (x)
#define SIZE 101
#define INF 1e18 + 9

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 2e9;
const ll linf = 2e18;

template <typename T>
ostream& operator << (ostream& s, vector<T>& v) {
    for (auto el : v) {
        s << el << " ";
    }
    return s;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll mod = 12345;

    int n; cin >> n;
    vector<vector<ll>> dp(n + 2, vector<ll>(2));
    dp[0][0] = 1;

    for (int i = 1; i <= n + 1; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
        if (i > 1) dp[i][1] += dp[i - 2][0];
        dp[i][0] %= mod;
        dp[i][1] %= mod;
    }
    cout << dp[n + 1][0] << endl;

    return 0;
}