#include <bits/stdc++.h>

#define MOD 666013
#define int long long

using namespace std;

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

//ifstream f("filesmodel.in");
//ofstream g("filesmodel.out");

int n;

int sol[2][2] = {
    {1,0},
    {0,1}
};

int p[2][2] = {
    {1,1},
    {1,0}
};

int tmp[2][2];

/// 1 1 * fn-1 = fn
/// 1 0   1n-2   fn-1

void prod(int c[2][2],int a[2][2],int b[2][2]){

    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            c[i][j] = 0;
            for(int k=0;k<2;k++){
                c[i][j] += (1ll*a[i][k]*b[k][j])%MOD;
                c[i][j] %= MOD;
            }
        }
    }

}

void eq(int a[2][2],int b[2][2]){

    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            a[i][j] = b[i][j];
        }
    }
}

signed main(){


    f>>n;

    if(n == 0){
        g<<0;
        return 0;
    }

    if(n == 1){
        g<<1;
        return 0;
    }

    n-=2;
    while(n!=0){

        if(n%2 == 1){
            prod(tmp,sol,p);
            eq(sol,tmp);
        }
        prod(tmp,p,p);
        eq(p,tmp);

        n/=2;
    }

    g<<sol[0][0] + sol[0][1];


    return 0;
}