#include <fstream>
#include <vector>
#define MOD 666013

using namespace std;

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

const int Nmax = 2;

int Mat[Nmax][Nmax], Sol[Nmax][Nmax];

void multiply (int A[Nmax][Nmax], int B[Nmax][Nmax])
{
    long long C[Nmax][Nmax];

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
    {
        C[i][j] = 0;
        for(int k = 0; k < 2; k++)
        C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
    }

      for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
          A[i][j] = C[i][j];
}

int main()
{
    int n;
    in >> n;

    if (n == 0)
    {
        out << 0;
        return 0;
    }

    n--;
    Mat[0][0] = 0;
    Mat[0][1] = 1;
    Mat[1][0] = 1;
    Mat[1][1] = 1;
    Sol[0][1] = 1;

    for (int i = 0; (1<<i) <= n; i++)
    {
        if ((1<<i) & n)
            multiply (Sol, Mat);
        multiply (Mat, Mat);
    }

    out << Sol[0][1];
    return 0;
}