#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
#define ll long long
#define PRIM 666013
ll c[2][2];


void square_matrix(ll a[][2],ll b[][2])
{
    c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%PRIM;
    c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%PRIM;
    c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%PRIM;
    c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%PRIM;
}

void matrixpower(ll Z[][2],ll k)
{
        if(k==1)
        {
            for(int i=0;i<2;i++)
            {
                for(int j=0;j<2;j++)
                {
                    c[i][j]=Z[i][j];
                }
            }
        }
        else
        {
            if(k%2==0)
            {
                matrixpower(Z,k/2);
                ll a[2][2], b[2][2];
                for(int i=0;i<2;i++)
                    for(int j=0;j<2;j++)
                    {
                        a[i][j]=c[i][j];
                        b[i][j]=c[i][j];
                    }
                square_matrix(a,b);
            }
            else
            {
                matrixpower(Z,k/2);
                ll a[2][2], b[2][2];
                for(int i=0;i<2;i++)
                    for(int j=0;j<2;j++)
                    {
                        a[i][j]=c[i][j];
                        b[i][j]=c[i][j];
                    }
                square_matrix(a,b);
                for(int i=0;i<2;i++)
                    for(int j=0;j<2;j++)
                    {
                        a[i][j]=c[i][j];
                        b[i][j]=Z[i][j];
                    }
                square_matrix(a,b);
            }
        }
}

int main()
{
    ll Z[2][2]={{0,1},{1,1}};
    ll k;
    in>>k;
    matrixpower(Z,k-1);
    out<<c[1][1]%PRIM;
    return 0;
}