#include<bits/stdc++.h>
using namespace std;


const int mod=666013;

struct matrix
{
    long long mat[2][2];
    matrix()//matrice identitate
    {
        for(int i=0; i<2; i++)
            for(int k=0; k<2; k++)
            {
                mat[i][k]=0;
            }
        mat[0][0]=1;
        mat[1][1]=1;

    }

    matrix operator*(const matrix&other)
    {
        matrix newmat;
        for(int y=0; y<2; y++)
        {
            for(int x=0; x<2; x++)
            {
                int sum=0;
                for(int k=0; k<2; k++)
                {
                    sum=(sum+mat[y][k]*other.mat[k][x])%mod;
                }
                newmat.mat[y][x]=sum;
            }
        }
        return newmat;
    }


};


matrix base;

void init_base()
{
    base.mat[0][0]=1;
    base.mat[0][1]=1;
    base.mat[1][0]=1;
    base.mat[1][1]=0;

}

void rapid_exponentiation(int n)
{
    matrix result;
    n--;
    for(int i=1; i<=n; i*=2)
    {
        if(n&i)
        {
            result=result*base;
        }
        base=base*base;
    }
    freopen("kfib.out","w",stdout);
    printf("%d\n",result.mat[0][0]);

}


int n;
void read()
{
    freopen("kfib.in","r",stdin);
    scanf("%d",&n);
}


int main()
{


    init_base();
    read();
    rapid_exponentiation(n);
}