#include <bits/stdc++.h>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int MOD = 666013;

struct Mat
{
    int mat[2][2];
};
const Mat I ={
         {{1, 0},
         {0, 1}}
};
const Mat init = {
        {{0, 1},
        {1, 1}}
};
Mat inmultire(Mat a, Mat b)
{
    Mat res;
    res.mat[0][0] = (1LL * a.mat[0][0] * b.mat[0][0] + 1LL * a.mat[0][1] * b.mat[1][0]) % MOD;
    res.mat[0][1] = ((1LL * a.mat[0][0] * b.mat[0][1]) % MOD + (1LL * a.mat[0][1] * b.mat[1][1]) % MOD) % MOD;
    res.mat[1][0] = ((1LL * a.mat[1][0] * b.mat[0][0]) % MOD + (1LL * a.mat[1][1] * b.mat[1][0]) % MOD) % MOD;
    res.mat[1][1] = ((1LL * a.mat[1][0] * b.mat[0][1]) % MOD + (1LL * a.mat[1][1] * b.mat[1][1]) % MOD) % MOD;
    return res;
}

int _power(int x, int p)
{
    int res = 1;
    while(p)
    {
        if(p%2)
            res = res * x;
        x *= x;
        p/=2;
    }
    return res;
}
Mat _power(Mat x, int k)
{
    Mat res = I;
    while(k)
    {
        if(k % 2)
            res = inmultire(res, x);
        x = inmultire(x, x);
        k/=2;
    }
    return res;
}

int main()
{
    int k;
    f >> k;
    g << _power(init, k).mat[0][1];
}