#include <iostream>
#include <fstream>

using namespace std;

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

int m[2][2];
const long long mod =666013;

void inmultire_matrice(int m[2][2],int n[2][2],int r[2][2])
{
    r[0][0]=(m[0][0]*n[0][0]%mod+m[0][1]*n[1][0]%mod)%mod;
    r[0][1]=(m[0][0]*n[0][1]%mod+m[0][1]*n[1][1]%mod)%mod;
    r[1][0]=(m[1][0]*n[0][0]%mod+m[1][1]*n[1][0]%mod)%mod;
    r[1][1]=(m[1][0]*n[0][1]%mod+m[1][1]*n[1][1]%mod)%mod;
}

void primire_matrice(int m[2][2],int n[2][2])
{
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            m[i][j]=n[i][j];
}

void ridicare_la_putere(long long k)
{
    if(k>0)
    {
        int y[2][2]={0},r[2][2];
        y[0][0]=y[1][1]=1;
        while(k>1)
        {
            if(k%2==0)
            {
                inmultire_matrice(m,m,r);
                primire_matrice(m,r);
                k=k/2;
            }
            else
            {
                inmultire_matrice(m,y,r);
                primire_matrice(y,r);
                inmultire_matrice(m,m,r);
                primire_matrice(m,r);
                k=(k-1)/2;
            }
        }
        inmultire_matrice(m,y,r);
        primire_matrice(m,r);
    }
}

int main()
{
    m[0][0]=0;
    m[0][1]=m[1][0]=m[1][1]=1;
    int r[2][2];
    long long k;
    fin>>k;
    int f0=0,f1=1;
    ridicare_la_putere(k-1);
    fout<<(f0*m[0][1]+f1*m[1][1]);
    return 0;
}