#include<fstream>
#define mod 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
long long n,x[3][3],rez[3][3],mat[3][3];
void mult(long long a[][3],long long b[][3],long long c[][3])
{
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            for(int k=1; k<=2; k++)
                c[i][j]=(c[i][j]+a[i][k]*b[j][k])%mod;
}
void exp(long long mat[][3],long long e,long long r[][3])
{
    if(e==0)
    {
        r[1][1]=r[2][2]=1;
        r[1][2]=r[2][1]=0;
        return ;
    }
    exp(mat,e/2,r);
    if(e%2==0)
    {
        long long a[3][3];
        a[1][1]=r[1][1];
        a[1][2]=a[2][1]=r[1][2];
        a[2][2]=r[2][2];
        r[1][1]=r[1][2]=r[2][1]=r[2][2]=0;
        mult(a,a,r);
    }
    else
    {
        long long a[3][3];
        a[1][1]=r[1][1];
        a[1][2]=a[2][1]=r[1][2];
        a[2][2]=r[2][2];
        r[1][1]=r[1][2]=r[2][1]=r[2][2]=0;
        mult(a,a,r);
        a[1][1]=r[1][1];
        a[1][2]=a[2][1]=r[1][2];
        a[2][2]=r[2][2];
        r[1][1]=r[1][2]=r[2][1]=r[2][2]=0;
        mult(a,mat,r);
    }
}

int main()
{
    cin>>n;
    mat[1][1]=0;
    mat[1][2]=mat[2][1]=mat[2][2]=1;
    exp(mat,n-1,rez);
            cout<<rez[2][2];
}