#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

typedef int matrix[5][5];

int n, p;

matrix A, I;

void clear_matrix(matrix A){
     for(int i = 1; i<=2; ++i)
        for(int j = 1; j<=2; ++j)
            A[i][j] = 0;
}

void copy_matrix(matrix FROM, matrix TO){
    for(int i = 1; i<=2; ++i)
        for(int j = 1; j<=2; ++j)
            TO[i][j] = FROM[i][j];
}


void multiply(matrix A, matrix B, matrix C){
    for(int i = 1; i<=2; ++i)
        for(int j = 1; j<=2; ++j){
            C[i][j] = 0;
            /// se inmulteste linia de la prima cu coloana de la a doua
            for(int k = 1; k<=2; ++k)
                C[i][j] += A[k][j] * B[i][k];
            C[i][j] %= MOD;
        }
}

void lgpow(matrix N, int p){
    matrix ANS, A, TEMP;
    copy_matrix(N, A);
    copy_matrix(I, ANS);
    while(p){
        if(p%2){
            multiply(ANS, A, TEMP);
            copy_matrix(TEMP, ANS);
        }
        p /= 2;

        multiply(A, A, TEMP);
        copy_matrix(TEMP, A);

    }

    copy_matrix(ANS, N);
}



int main()
{
    A[1][2] = 1;
    A[2][1] = 1;
    A[2][2] = 1;

    I[1][1] = 1;
    I[2][2] = 1;

    fin >> n;
    matrix TEMP; clear_matrix(TEMP);

    lgpow(A, n-1);

    fout << A[2][2];

    return 0;
}