#include <bits/stdc++.h>
using namespace std;
typedef int matr[3][3];
#define MOD 666013
int m=2;
matr fibo,aux,rez;

void inm(matr a, matr b, matr rez){
    // face rez = a*b
    int i,j,k;
    for(i=1;i<=m;i++){
        for(j=1;j<=m;j++){
            aux[i][j] = 0;
            for(k=1;k<=m;k++){
                aux[i][j] += (1LL*a[i][k]*b[k][j]) % MOD;
                if(aux[i][j] >= MOD)
                    aux[i][j]-=MOD;
            }
        }
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
            rez[i][j]=aux[i][j];
}

void lgpow(matr b, int e, matr rez){
    int i,j;
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
            rez[i][j]=(i==j);
    while(e){
        if(e&1)
            inm(b,rez,rez);
        inm(b,b,b);
        e/=2;
    }
}


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

    int n;
    fin>>n;
    fibo[1][1]=1;
    fibo[1][2]=1;
    fibo[2][1]=1;
    fibo[2][2]=0;

    lgpow(fibo,n,rez);
    fout<<rez[2][1];

    return 0;
}