#include <fstream>

#define ll long long
#define MOD 666013
using namespace std;

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

int m[2][2] =
{
    { 0, 1},
    { 1, 1},
};
;
int f[2][2] =
{
    { 0, 1},
    { 1, 1},
};
;
void inmultire(int a[2][2], int b[2][2])
{
    int aux[2][2], auxb[2][2];

    aux[0][0] = a[0][0];
    aux[0][1] = a[0][1];
    aux[1][0] = a[1][0];
    aux[1][1] = a[1][1];

    auxb[0][0] = b[0][0];
    auxb[0][1] = b[0][1];
    auxb[1][0] = b[1][0];
    auxb[1][1] = b[1][1];

    a[0][0] = (aux[0][0]*auxb[0][0] + aux[0][1]*auxb[1][0]) % MOD;
    a[0][1] = (aux[0][0]*auxb[0][1] + aux[0][1]*auxb[1][1]) % MOD;
    a[1][0] = (aux[1][0]*auxb[0][0] + aux[1][1]*auxb[1][0]) % MOD;
    a[1][1] = (aux[1][0]*auxb[0][1] + aux[1][1]*auxb[1][1]) % MOD;
}
void exp(int a[2][2], int k)
{
    int aux;
    if (k == 1) return;
    if (k % 2)
    {
        inmultire(a,m);
        exp(a,k-1);
    }
    else
    {
        exp(a,k/2);
        inmultire(a,a);
    }
}
int main()
{
    int k;
    fin>>k;

    exp(f, k-1);

    fout<<f[1][1] % MOD<<'\n';

    fin.close();
    fout.close();
    return 0;
}