#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

struct matrice{
    int m[2][2];
    matrice(){
        memset(m, 0, sizeof(m));
    }
    friend matrice operator* (matrice a, matrice b)
    {
    matrice ans;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                ans.m[i][j] = (ans.m[i][j]+1LL*a.m[i][k]*b.m[k][j])%666013;
    return ans;
    }

};

matrice m1, im;



matrice pow(matrice x, int n)
{
    if(n==0)
        return im;
    if(n&1)
        return x*pow(x*x, n>>1);
    return pow(x*x, n>>1);
}
int main()
{
    int n;
    fin>>n;

    m1.m[0][0]=m1.m[1][0]=m1.m[0][1]=1;
    m1.m[1][1]=0;

    im.m[0][0]=im.m[1][1]=1;
    im.m[1][0]=im.m[0][1]=0;

    if(n<=1)
        fout<<1;
    else{
        matrice r;

        r.m[0][1] = r.m[1][1]=0;
        r.m[1][0] = r.m[0][0]=1;
        m1= pow(m1, n-2);
        matrice ans;
        ans=m1*r;
        fout<<ans.m[0][0];
    }

    return 0;
}