#include <bits/stdc++.h>

using namespace std;
int mod=666013;
struct matrice
{
    long long m[3][3];
};
matrice M;
matrice Inmult_matrici(matrice A, matrice B)
{
    matrice rasp;
    for(int i=0; i<=1; i++)
    {
        for(int j=0; j<=1; j++)
        {
            rasp.m[i][j]=0;
            for(int k=0; k<=1; k++)
            {
                rasp.m[i][j]=(rasp.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
            }
        }
    }
    return rasp;
}
matrice exp_rapida(matrice A, int put)
{
    matrice rasp;
    rasp.m[0][0]=1;
    rasp.m[0][1]=0;
    rasp.m[1][0]=0;
    rasp.m[1][1]=1;
    ///I2
    while(put>0)
    {
        if(put%2==1)
            rasp = Inmult_matrici(rasp, M);
        M = Inmult_matrici(M, M);
        put/=2;
    }
    return rasp;
}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    ///fie matricea patrata M = (0 1, 1 1)
    ///F0 = 0, F1 = 1
    ///putem afla orice termen Fk prin formula:
    ///vectorul (F0, F1) * M^k = (Fk, F(k+1))
    ///facem exponentiere rapida pt a calcula M^k
    ///daca inmultim vectorul (0,1) cu o matrice (a b, c d) rezultatul va fi (b, d)
    ///noi vom face inmultirea (0, 1) * M^k = (Fk, F(k+1))
    ///ne intereseaza doar Fk, adica M^k[0][1]
    int n;
    cin>>n;
    M.m[0][0]=0;
    M.m[0][1]=1;
    M.m[1][0]=1;
    M.m[1][1]=1;
    matrice M_ridicat = exp_rapida(M, n);
    if(n==0)
        cout<<0;
    else if(n==1)
        cout<<1;
    else
        cout<<M_ridicat.m[1][0];
    return 0;
}