#include <fstream>
#include <cstring>

#define MOD 666013

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

int sol[3][3];

void mult(int sol[][3], int m[][3]){
    int C[3][3]={};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + 1LL * sol[i][k] * m[k][j]) % MOD;
    memcpy(sol, C, sizeof(C));
}

void power(int M[][3], int power){
    for(int i = 1; i <= power; i <<= 1){
        if(power & i){
            mult(sol, M);
        }

        mult(M, M);
    }
}

int main()
{
    int M[3][3];
    int n;
    fin >> n;
    M[0][0] = 0;
    M[0][1] = 1;
    M[1][0] = 1;
    M[1][1] = 1;
    sol[0][0] = sol[1][1] = 1;

    power(M, n - 1);

    fout << sol[1][1];

    return 0;
}