#include <iostream>
#include <fstream>
#define m 666013

using namespace std;

long long sol[2][2], a[2][2];

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

int produs_par()
{
    long long rez[2][2];
    rez[0][0] = (a[0][0] * a[0][0] + a[0][1] * a[1][0])%m;
    rez[0][1] = (a[0][0] * a[0][1] + a[0][1] * a[1][1])%m;
    rez[1][0] = (a[1][0] * a[0][0] + a[1][1] * a[1][0])%m;
    rez[1][1] = (a[1][0] * a[0][1] + a[1][1] * a[1][1])%m;
    a[0][0] = rez[0][0] % m;
    a[0][1] = rez[0][1] % m;
    a[1][0] = rez[1][0] % m;
    a[1][1] = rez[1][1] % m;
}
int produs_impar()
{
    long long rez[2][2];
    rez[0][0] = (sol[0][0] * a[0][0] + sol[0][1] * a[1][0])%m;
    rez[0][1] = (sol[0][0] * a[0][1] + sol[0][1] * a[1][1])%m;
    rez[1][0] = (sol[1][0] * a[0][0] + sol[1][1] * a[1][0])%m;
    rez[1][1] = (sol[1][0] * a[0][1] + sol[1][1] * a[1][1])%m;
    sol[0][0] = rez[0][0] % m;
    sol[0][1] = rez[0][1] % m;
    sol[1][0] = rez[1][0] % m;
    sol[1][1] = rez[1][1] % m;

}
///  10    01
///  01    11
int exponent(int k)
{
    while(k)
    {
        if(k % 2 == 0)
        {
            produs_par();
            k = k / 2;
        }
        else
        {
            produs_impar();
            k--;
        }
    }
}

int main()
{
    long long k;
    f >> k;
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    exponent(k - 1);
    g << sol[1][1];
}