#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
ifstream fi("kfib.in");
ofstream fo("kfib.out");

struct Mat
{
    long long a11, a12, a21, a22;
};

Mat LgPut(Mat a, int n)
{
    Mat sol;
    sol.a11 = 1;
    sol.a12 = 0;
    sol.a21 = 0;
    sol.a22 = 1;
    Mat aux;
    while(n)
    {
        if( n & 1)
        {
            aux = sol;
            sol.a11 = (aux.a11 * a.a11 + aux.a12 * a.a21)% MOD;
            sol.a12 = (aux.a11 * a.a12  + aux.a12 * a.a22)% MOD;
            sol.a21 = (aux.a21 * a.a11  + aux.a22 * a.a21)% MOD;
            sol.a22 = (aux.a12 * a.a21 + aux.a22 * a.a22)% MOD;
        }

        n /= 2;
        aux = a;
        a.a11 = (aux.a11 * aux.a11 + aux.a12 * aux.a21)% MOD;
        a.a12 = (aux.a11 * aux.a12  + aux.a12 * aux.a22)% MOD;
        a.a21 = (aux.a21 * aux.a11  + aux.a22 * aux.a21)% MOD;
        a.a22 = (aux.a12 * aux.a21 + aux.a22 * aux.a22)% MOD;
    }
    return sol;
}
int main()
{
    int n;
    fi>>n;
    Mat s;
    s.a11 = 1;
    s.a12 = 1;
    s.a21 = 1;
    s.a22 = 0;
    s = LgPut(s,n-1);
    fo << s.a11;
}