#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void inmulteste(long long a[2][2], long long b[2][2])
{
    long long c[2][2]={
    a[0][0], a[0][1],
    a[1][0], a[1][1],
    };
    c[0][0]=(a[0][0]*b[0][0] + a[0][1]* b[1][0])%666013;
    c[0][1]=(a[0][0]*b[0][1] + a[0][1]* b[1][1])%666013;
    c[1][0]=(a[1][0]*b[0][0] + a[1][1]* b[1][0])%666013;
    c[1][1]=(a[1][0]*b[0][1] + a[1][1]* b[1][1])%666013;
    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];

}
int fortza(long long b[][2], int e)
{
    long long rez[2][2]=
    {
        1, 0,
        0, 1,
    };
    while(e)
    {
        if(e%2==1)
        inmulteste(rez, b);
        e/=2;
        inmulteste(b, b);
    }
    return rez[0][1];

}
int main()
{
    long long a[2][2]=
    {
        1, 1,
        1, 0,
    };
    long long n;
    fin>>n;
    fout<<fortza(a, n);
    return 0;
}