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

using namespace std;

struct matrix{
    int l, c;
    long long int a[3][3];
};

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

matrix inmultire(matrix a, matrix b)
{
    matrix c;
    c.l = a.l;
    c.c = b.c;
    for (int i = 1; i <= a.l; i++)
        for (int j = 1; j <= b.c; j++)
        {
              c.a[i][j] = 0;
              for (int k = 1; k <= a.c; k++)
                c.a[i][j] += (a.a[i][k] * 1LL * b.a[k][j]) % MOD;
        }
    return c;
}

matrix ridicare(matrix a, int b)
{
    if(b != 1)
    {
        if (b % 2 == 0)
        {
            matrix c = ridicare(a, b/2);
            return inmultire(c, c);
        }
        else
            return inmultire(a, ridicare(a, b - 1));
    }
    return a;
}

int main()
{
    in >> k;
    in.close();
    matrix x;
    x.l = 1;
    x.c = 2;
    x.a[1][1] = 0;
    x.a[1][2] = 1;
    if (k == 0 || k == 1)
    {
        out << x.a[1][k + 1] << "\n";
        return 0;
    }
    matrix A;
    A.l = 2;
    A.c = 2;
    A.a[1][1] = 0;
    A.a[1][2] = 1;
    A.a[2][1] = 1;
    A.a[2][2] = 1;
    A = ridicare(A, k - 1);
    x = inmultire(x, A);
    out << x.a[1][2] % MOD << "\n";
    out.close();
    return 0;
}