#include <fstream>

#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

int k;
long long int ones[5][5], a[5][5];

void getPower(long long int a[5][5], int power) {

    if (power == 1) {

        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                a[i][j] = ones[i][j];

        return ;
    }

    long long int logMatrix[5][5];
    long long int b[5][5];

    b[1][1] = logMatrix[1][1] = 0;
    b[1][2] = logMatrix[1][2] = 0;
    b[2][1] = logMatrix[2][1] = 0;
    b[2][2] = logMatrix[2][2] = 0;


    getPower(logMatrix, power / 2);

    for (int i = 1; i <= 2; i++) {

        for (int j = 1; j <= 2; j++) {

            for (int t = 1; t <= 2; t++)
                b[i][j] = (b[i][j] + (logMatrix[i][t] * logMatrix[t][j]) % MOD) % MOD;
        }
    }

    if (power % 2 == 1) {

        for (int i = 1; i <= 2; i++) {

            for (int j = 1; j <= 2; j++) {

                for (int t = 1; t <= 2; t++)
                    a[i][j] = (a[i][j] + b[i][t] * ones[t][j]) % MOD;
            }
        }

    } else {

        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                a[i][j] = b[i][j];
    }
}

int main()
{
    f >> k;

    if (k == 1 || k == 2) {

        g << "1\n";
        return 0;
    }

    ones[1][1] = 0;
    ones[2][1] = 1;
    ones[1][2] = 1;
    ones[2][2] = 1;

    getPower(a, k - 2);

    g << (a[1][2] + a[2][2]) % MOD << "\n";

    return 0;
}