#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int K,A[2][2],B[2][2];
#define MOD 666013
void afis(int a[2][2])
{
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<=1;j++) g<<a[i][j]<<' ';
        g<<endl;
    }
    g<<endl;
}
void inm(int a[2][2], int b[2][2], int c[2][2])
{

    int d[2][2];
    d[0][0]=(a[0][0]*b[0][0]%MOD+a[0][1]*b[1][0]%MOD)%MOD;
    d[0][1]=(a[0][0]*b[0][1]%MOD+a[0][1]*b[1][1]%MOD)%MOD;
    d[1][0]=(a[1][0]*b[0][0]%MOD+a[1][1]*b[1][0]%MOD)%MOD;
    d[1][1]=(a[1][0]*b[0][1]%MOD+a[1][1]*b[1][1]%MOD)%MOD;


    c[0][0]=d[0][0];c[0][1]=d[0][1];c[1][0]=d[1][0];c[1][1]=d[1][1];


}


void Alan(int a[2][2], int b[2][2], int n)
{
    if(n==0){
        b[0][0]=b[1][1]=1;
        b[0][1]=b[1][0]=0;
    }
    else if(n==1) {
        b[0][0]=a[0][0];
        b[0][1]=a[0][1];
        b[1][0]=a[1][0];
        b[1][1]=a[1][1];
    }
         else {
            int c[2][2];
            Alan(a,c,n/2);
            if(n%2==0) inm(c,c,b);
            else {
                inm(c,c,b);
                inm(b,a,b);
            }
         }

}

int main()
{
    f>>K;
    A[0][0]=0;
    A[1][0]=A[0][1]=A[1][1]=1;
    Alan(A,B,K-1);

    if(B[1][1]<0) B[1][1]+=MOD;
    g<<B[1][1]<<'\n';
    f.close();
    g.close();
    return 0;
}