#include <fstream>
#include <iostream>
#define M 666013
using namespace std;

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

void exp(long long base[2][2], long e, long long** res)
{
    //cout<<base[0][0]<<' '<<base[0][1]<<'\n'<<base[1][0]<<' '<<base[1][1]<<'\n';
    if (e==0)
    {
        res[0][0] = 1;
        res[0][1] = 0;
        res[1][0] = 0;
        res[1][1] = 1;
    }
    else if (e==1)
    {
        res[0][0] = base[0][0]%M;
        res[0][1] = base[0][1]%M;
        res[1][0] = base[1][0]%M;
        res[1][1] = base[1][1]%M;
    }
    else
    {
        long long **r;
        r = new long long*[2];
        r[0] = new long long[2];
        r[1] = new long long[2];
        exp(base, e/2, r);
        int tmp[2][2];
        tmp[0][0] = (r[0][0]*r[0][0] + r[0][1]*r[1][0])%M;
        tmp[0][1] = (r[0][0]*r[0][1] + r[0][1]*r[1][1])%M;
        tmp[1][0] = (r[1][0]*r[0][0] + r[1][1]*r[1][0])%M;
        tmp[1][1] = (r[1][0]*r[0][1] + r[1][1]*r[1][1])%M;
        if (e%2)
        {
            res[0][0] = (tmp[0][0]*base[0][0] + tmp[0][1]*base[1][0])%M;
            res[0][1] = (tmp[0][0]*base[0][1] + tmp[0][1]*base[1][1])%M;
            res[1][0] = (tmp[1][0]*base[0][0] + tmp[1][1]*base[1][0])%M;
            res[1][1] = (tmp[1][0]*base[0][1] + tmp[1][1]*base[1][1])%M;
        }
        else
        {
            res[0][0] = tmp[0][0];
            res[0][1] = tmp[0][1];
            res[1][0] = tmp[1][0];
            res[1][1] = tmp[1][1];
        }
    }
}

int main()
{
    int N;
    f>>N;
    long long m[2][2];
    m[0][0] = m[0][1] = m[1][0] = 1;
    m[1][1] = 0;
    long long **er;
    er = new long long*[2];
    er[0] = new long long[2];
    er[1] = new long long[2];
    exp(m, N, er);
    g<<er[0][1];
}