#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const int64_t MOD = 666013;

vector<vector<int64_t>> multiply(vector<vector<int64_t>> a, vector<vector<int64_t>> b)
{
    vector<vector<int64_t>> c;
    c.resize(2);
    c[0].resize(2);
    c[1].resize(2);

    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
                c[i][j] += ((a[i][k] % MOD) * (b[k][j] % MOD)) % MOD;
            c[i][j] %= MOD;
        }
    }

    return c;
}

void print(vector<vector<int64_t>> a)
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}

vector<vector<int64_t>> logPow(vector<vector<int64_t>> x, int n)
{
    vector<vector<int64_t>> p;

    p.resize(2);

    p[0].push_back(1);
    p[0].push_back(0);
    p[1].push_back(0);
    p[1].push_back(1);

    while(n)
    {
        if(n & 1)
            p = multiply(p, x);

        x = multiply(x, x);
        n >>= 1;
    }

    return p;
}

int main()
{
    vector<vector<int64_t>> basic;

    basic.resize(2);

    basic[0].push_back(0);
    basic[0].push_back(1);
    basic[1].push_back(1);
    basic[1].push_back(1);

    int k;
    in >> k;

    vector<vector<int64_t>> ans = logPow(basic, k - 1);

    out << ((ans[0][0] % MOD) + (ans[0][1] % MOD)) % MOD << '\n';

    return 0;
}