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

using namespace std;

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


int k;
int mat[5][5];
int sol[5][5];

void prod (int n, int m, int a[5][5], int nn, int mm, 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 (){
    sol[1][1]=0;
    sol[1][2]=1;

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

    fin>>k; if(k == 0){fout<<0;return 0;}
    k--;
    while(k != 0){
        if(k%2 == 1)
            prod(1, 2, sol, 2, 2, mat);

        prod(2, 2, mat, 2, 2, mat);
        k/=2;
    }

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