#include<iostream>
#include<fstream>
using namespace std;
long long A[2][2],n,P[2][2], X[2][2];
void inmultire(long long a[2][2], long long b[2][2], long long c[2][2])
{
    long long i,j,k,s;
    for(i=0;i<=1;i++)
    {
        for(j=0;j<=1;j++)
        {
            s=0;
            for(k=0;k<=1;k++)
            {
                s=(s+a[i][k]*b[k][j])%666013;
            }
            c[i][j]=s;
        }
    }
}
void copiez(long long a[2][2], long long b[2][2])
{
    long long i,j;
    for(i=0;i<=1;i++)
    {
        for(j=0;j<=1;j++)
        {
            a[i][j]=b[i][j];
        }
    }
}
int main()
{
    long long i,j;
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin>>n;
    for(i=0;i<=1;i++)
    {
        P[i][i]=1;
        for(j=0;j<=1;j++)
        {
            A[i][j]=1;
        }
    }
    A[0][0]=0;

    /*for(i=1;i<=n;i++)
    {
        inmultire(P,A,X);
        copiez(P,X);
    }*/
    while(n!=0)
    {
        if(n%2==1)
        {
            inmultire(P,A,X);
            copiez(P,X);
        }
        inmultire(A,A,X);
        copiez(A,X);
        n=n/2;
    }
    fout<<P[0][1];
    fin.close();
    fout.close();
    return 0;
}