#include <bits/stdc++.h>
using namespace std;

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

const int MOD=666013;

int mmult(long long a, long long b) {
    long long p=a*b;
    if(p>=MOD) {
        p=p-1LL*MOD*(p/MOD);
    }
    return p;
}

int madd(int a, int b) {
    int s=a+b;
    if(s>=MOD)
        s=s-MOD;
    return s;
}

struct matrix {
    int** val;
    int lin, col;
    matrix(int x, int y) {
        lin=x;
        col=y;
        val=new int*[x];
        for(int i=0;i<x;++i)
            val[i]=new int[y];
    }

    int* operator[](int i) {
        return val[i];
    }

    matrix operator*(matrix& b) {
        matrix c(lin, b.col);
        for(int i=0;i<c.lin;++i) {
            for(int j=0;j<c.col;++j) {
                c[i][j]=0;
                for(int k=0;k<col;++k) {
                    c[i][j]=madd(c[i][j], mmult(val[i][k], b[k][j]));
                }
            }
        }
        return c;
    }
};

matrix identity(int n) {
    matrix c(n, n);
    for(int i=0;i<n;++i) {
        for(int j=0;j<i;++j)
            c[i][j]=0;
        c[i][i]=1;
        for(int j=i+1;j<n;++j)
            c[i][j]=0;
    }
    return c;
}

matrix init1() {
    matrix a(2, 2);
    a[0][0]=0;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=1;
    return a;
}

matrix init2() {
    matrix c(2, 1);
    c[0][0]=0;
    c[1][0]=1;
    return c;
}

matrix pow(matrix a, long long k) {
    if(k==0)    return identity(a.col);
    if(k&1)     return pow(a*a, k>>1)*a;
    return pow(a*a, k>>1);
}

int main() {
    long long n;
    fin>>n;
    if(n==0) {
        fout<<0;
        return 0;
    }
    matrix a(2, 2), c(2, 1);
    c=init2();
    a=init1();
    a=pow(a, n-1);
    c=a*c;
    fout<<c[1][0]<<'\n';
    return 0;
}