#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const long long modulo =  666013;

int k;

void mult(long long a[5][5], long long b[5][5], long long c[5][5]) {
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            c[i][j]=0;
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            for(int k=1;k<3;k++)
                c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%modulo)%modulo;
}

void atrib(long long a[5][5], long long b[5][5]) {
    a[1][1]=b[1][1];
    a[1][2]=b[1][2];
    a[2][1]=b[2][1];
    a[2][2]=b[2][2];
}

int main() {
    long long sol[5][5],a[5][5],b[5][5];
    f>>k;
    k-=2;
    sol[1][2]=sol[2][1]=0;
    sol[1][1]=1;
    sol[2][2]=1;
    a[1][1]=a[1][2]=a[2][1]=1;
    a[2][2]=0;
    while(k!=0) {
        if((k&1)==1) {
            mult(sol,a,b);
            atrib(sol,b);
        }
        k>>=1;
        mult(a,a,b);
        atrib(a,b);
    }
    g<<(sol[1][1]%modulo+sol[1][2]%modulo)%modulo<<"\n";
    return 0;
}