#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;
long long b[3][3],a[3][3],rasp[3][3],c[3][3],aux[3][3];
long long n;

long long lgput(long long put)
{
    while(put!=0)
    {
        if(put%2==1)
        {
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    aux[i][j]=0;
              for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    for(int k=1;k<=2;k++)
                        aux[i][j]=(aux[i][j]+b[i][k]*a[k][j])%MOD;
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                        b[i][j]=aux[i][j];
            put--;
        }
        else if(put%2==0)
        {
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                {
                    aux[i][j]=a[i][j];
                    a[i][j]=0;
                }
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    for(int k=1;k<=2;k++)
                        a[i][j]=(a[i][j]+aux[i][k]*aux[k][j])%MOD;
            put/=2;
        }
    }
}

int main()
{
    b[1][1]=b[2][2]=1;
    a[1][1]=a[1][2]=a[2][1]=1;
    a[2][2]=c[2][1]=0;
    c[1][1]=1;
    fin >> n;
    lgput(n-1);
    for(int i=1;i<=2;i++)
        for(int j=1;j<=1;j++)
            for(int k=1;k<=2;k++)
                rasp[i][j]=(rasp[i][j]+b[i][k]*c[k][j])%MOD;
    fout << rasp[1][1]%MOD;
    return 0;
}