#include <bits/stdc++.h>

#define NM_MAX 2
#define ll long long

using namespace std;

const int MOD = 666013;
const ll MOD2 = 1LL * MOD * MOD;

struct Matrix
{
    int n, m;
    int ma[NM_MAX][NM_MAX];
};

Matrix operator * (Matrix a, Matrix b)
{
    Matrix ans;
    ans.n = a.n;
    ans.m = b.m;
    for(int i = 0; i < a.n; i++)
        for(int j = 0; j < b.m; j++)
        {
            ll sum = 0;
            for(int k = 0; k < a.m; k++)
            {
                sum += 1LL * a.ma[i][k] * b.ma[k][j] % MOD2;
                if(sum >= MOD2)
                    sum -= MOD2;
            }
            ans.ma[i][j] = sum % MOD;
        }
    return ans;
}

Matrix pwr (Matrix a, int b)
{
    if(b == 1)
        return a;
    if(b & 1)
        return pwr(a, b - 1) * a;
    Matrix p = pwr(a, (b >> 1));
    return p * p;
}

int k;

Matrix init, rec;

int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    init = Matrix{2, 1, {{0}, {1}}};
    rec = Matrix{2, 2, {{1, 1}, {1, 0}}};
    fin >> k;
    if(k == 0)
        fout << "0\n";
    else
        fout << (pwr(rec, k) * init).ma[0][0] << "\n";
    return 0;
}