#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

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

int k;
int v[5][5], mat[5][5];

void prod(int n, int m, int a[5][5], int b[5][5]){
    int c[5][5];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            c[i][j]=0;
            for(int l=1; l<=m; l++)
                c[i][j] = (c[i][j] + 1LL * a[i][l] * b[l][j] % MOD) % MOD;
        }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            a[i][j]=c[i][j];
}

int main (){
    fin>>k; if(k == 0){fout<<0; return 0;}

    v[1][1]=0;
    v[1][2]=1;
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;


    k--;
    while(k != 0){
        if(k%2 == 1)
            prod(1, 2, v, mat);
        prod(2, 2, mat, mat);
        k/=2;
    }

    fout<<v[1][2];
    return 0;
}

/**
(f[i-1], f[i]) * (0, 1) = (0*f[i-1] + 1*f[i], 1*f[i-1] + 1*f[i]) = (f[i], f[i-1] + f[i]) = (f[i], f[i+1]);
                 (1, 1)
**/