#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 inm(int a[2][2], int b[2][2], int c[2][2])
{
    c[0][0]=((a[0][0]*b[0][0])%MOD+(a[0][1]*b[1][0])%MOD)%MOD;
    c[0][1]=((a[0][0]*b[0][1])%MOD+(a[0][1]*b[1][1])%MOD)%MOD;
    c[1][0]=((a[1][0]*b[0][0])%MOD+(a[1][1]*b[1][0])%MOD)%MOD;
    c[1][1]=((a[1][0]*b[0][1])%MOD+(a[1][1]*b[1][1])%MOD)%MOD;
}

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;
}