#include <bits/stdc++.h>
#define MOD 666013

using namespace std;
ifstream fi("kfib.in");
ofstream fo("kfib.out");
int k;
unsigned long long M[2][2]={{0,1},{1,1}},Z[2][2]={{0,1},{1,1}};

void multiply(unsigned long long A[2][2], unsigned long long B[2][2])
{
    unsigned long long a,b,c,d;
    a=A[0][0]*B[0][0]%MOD + A[0][1]*B[1][0]%MOD;
    b=A[0][0]*B[0][1]%MOD + A[0][1]*B[1][1]%MOD;
    c=A[1][0]*B[0][0]%MOD + A[1][1]*B[1][0]%MOD;
    d=A[1][0]*B[0][1]%MOD + A[1][1]*B[1][1]%MOD;
    M[0][0]=a%MOD;
    M[0][1]=b%MOD;
    M[1][0]=c%MOD;
    M[1][1]=d%MOD;
}

void lgput(int p)
{
    if(p==1)
        return;
    if(p&1)
    {
        lgput(p-1);
        multiply(M,Z);
    }
    else
    {
        lgput(p/2);
        multiply(M,M);
    }
}

int main()
{
    fi>>k;
    if(k<=1)
        fo<<k;
    else
    {
        lgput(k-1);
        fo<<M[1][1];
    }
    fi.close();
    fo.close();
    return 0;
}