#include <fstream>
#define p 666013
#define DIM 3
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k, a[DIM][DIM] = {{0,0,0},{0,0,1},{0,1,1}},
       v[DIM][DIM] = {{0,0,0},{0,1,0},{0,0,1}}, c[DIM][DIM];

void copy(long long v1[DIM][DIM], long long v2[DIM][DIM], int n){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            v1[i][j]=v2[i][j];
}

void inm(long long x[DIM][DIM], long long y[DIM][DIM], int n){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            c[i][j]=0;
            for(int k=1; k<=n; k++)
                c[i][j]=(c[i][j]+x[i][k]*y[k][j])%p;
        }
    copy(x, c, n);
}

int main(){
    fin>>k;
    k-=2;
    while(k>0)
    {
        if(k%2)
            inm(v, a, 2);
        inm(a, a, 2);
        k/=2;
    }
    fout<<(v[2][1]+v[2][2])%p<<"\n";
    return 0;
}