#include <fstream>
#define MOD 666013
using namespace std;

void inmultireMatr(int a[][2], int b[][2], int n=2){
    int rez[2][2]={0, 0, 0, 0};
    for(int i=0; i<n; i++)
        for(int j=0; j<2; j++){
            for(int k=0; k<n; k++)
                rez[i][j]=(rez[i][j]+(a[i][k]*b[k][j])%MOD)%MOD;
        }
    for(int i=0; i<n; i++)
        for(int j=0; j<2; j++)
            a[i][j]=rez[i][j];
    return;
}

void ridPut(int a[][2], int put){
    int m[2][2]={1, 1, 1, 0};
    while(put){
        if(put%2){
            inmultireMatr(m, a);
        }
        inmultireMatr(a, a);
        put/=2;
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j]=m[i][j];
    return;
}

int main()
{
    int k;
    ifstream f("kfib.in");
    f>>k;
    f.close();
    int rez[2][2]={1, 0, 0, 0}, m[2][2]={1, 1, 1, 0};
    ofstream g("kfib.out");
    if(k==0){g<<0; return 0;}
    if(k==1){g<<1; return 0;}
    if(k==2){g<<1; return 0;}
    ridPut(m, k-2);
    inmultireMatr(rez, m, 1);
    g<<rez[0][0];
    g.close();
    return 0;
}