#include <iostream>
#include <fstream>

using namespace std;

long long a[6][6],b[6][6];

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void mult(long long x[6][6],long long y[6][6])
{
    long long c[6][6];
    c[1][1]=(x[1][1]*y[1][1])%666013+(x[1][2]*y[2][1])%666013;
    c[1][2]=(x[1][1]*y[1][2])%666013+(x[1][2]*y[2][2])%666013;
    c[2][1]=(x[2][1]*y[1][1])%666013+(x[2][2]*y[2][1])%666013;
    c[2][2]=(x[2][1]*y[1][2])%666013+(x[2][2]*y[2][2])%666013;
    b[1][1]=c[1][1]%666013;
    b[1][2]=c[1][2]%666013;
    b[2][1]=c[2][1]%666013;
    b[2][2]=c[2][2]%666013;
}

void ridicare(long long p)
{
    if(p!=1)
    {
        ridicare(p/2);
        if(p%2==1)
        {
            mult(b,b);
            mult(b,a);
        }
        else
            mult(b,b);
    }
    else
    {
        b[1][1]=b[1][2]=b[2][1]=1;
        b[2][2]=0;
    }
}

int main()
{
    long long n;
    a[1][1]=a[1][2]=a[2][1]=1;
    a[2][2]=0;
    fin>>n;
    if(n==1)
    {
        fout<<1;
        return 0;
    }
    ridicare(n-1);
    fout<<b[1][1];
    return 0;
}