#include <iostream>
#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int MOD = 666013;

void inmultMatrix(long long matrRes[][3], long long matrSec[][3]){
    long long a = ((matrRes[0][0] * matrSec[0][0]) % MOD + (matrRes[0][1] * matrSec[1][0]) % MOD) % MOD;
    long long b = (matrRes[0][0]* matrSec[0][1] % MOD + matrRes[0][1] *  matrSec[1][1] % MOD) % MOD;
    long long c = ( matrRes[1][0] * matrSec[0][0] % MOD + matrRes[1][1] * matrSec[1][0] % MOD ) % MOD;
    long long d = ( matrRes[1][0] * matrSec[0][1] % MOD + matrRes[1][1] * matrSec[1][1] % MOD) % MOD;
    matrRes[0][0] = a;
    matrRes[0][1] = b;
    matrRes[1][0] = c;
    matrRes[1][1] = d;
    // aici faci inmultirea folosind modulul, o inmultire de matrice patratice de n = 2

}
long long poweredMatrixInLog(int power)
{
    long long initMatrix[][3] = {{0,1},
                          {1,1}};
    long long wantedMatrix[][3] = {{1, 0}, {0, 1}};
    // inmultirea in timp logaritmic a matricilor
    // nu e nevoie refolosirea lor, deci nu refolosim
    // daca vrem refolosirea atuncea bagam o matrice ceva de genul matrix[20][3][3];
    // si la fiecare putere memoram matricea rezultata in inmultire
    while(power != 0){
        if(power % 2 == 1){
            inmultMatrix(wantedMatrix, initMatrix);
            --power;
        }
        inmultMatrix(initMatrix, initMatrix);
        power = power / 2;
    }
    return (wantedMatrix[0][0] + wantedMatrix [1][0]) % MOD;
}

long long fib(long long n)
{
    return poweredMatrixInLog(n - 1);

}
int main()
{
    int n;
    fin>>n;
    fout<<fib(n);
    return 0;
}