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

using namespace std;

int n;
int x[3][3], p[3][3];

inline void ExpLog(void)
{
    p[1][1] = p[2][2] = 1;
    x[1][2] = x[2][1] = x[2][2] = 1;

    int i, j, k, mat[3][3];
    long long nr;
    while (n)
    {
        if (n & 1)
        {
            /// p = p*x;
            for (i=1; i<=2; i++)
                for (j=1; j<=2; j++)
                {
                    nr = 0LL;
                    for (k=1; k<=2; k++)
                        nr += (1LL * p[i][k] * x[k][j]);
                    mat[i][j] = nr % MOD;
                }
            for (i=1; i<=2; i++)
                for (j=1; j<=2; j++)
                    p[i][j] = mat[i][j];
            n--;
        }
        ///x = x*x
        for (i=1; i<=2; i++)
            for (j=1; j<=2; j++)
            {
                nr = 0LL;
                for (k=1; k<=2; k++)
                    nr += (1LL * x[i][k] * x[k][j]);
                mat[i][j] = nr % MOD;
            }
        for (i=1; i<=2; i++)
            for (j=1; j<=2; j++)
                x[i][j] = mat[i][j];
        n >>= 1;
    }
}

int main()
{
    ifstream f ("kfib.in");
    f>>n;
    f.close();
    n-=2;
    ExpLog();
    ofstream g("kfib.out");
    g<<(1LL * p[1][2] + 1LL * p[2][2])%MOD<<"\n";
    g.close();
    return 0;
}