#include <bits/stdc++.h>
#define P 666013
using namespace std;

/**
f[1] = f[2] = 1;
f[n] = f[n-1] + f[n-2], n>=3

Sa se calc. al n-lea termen Fibonacci
adica pe f[n] % P, unde n <= 10^9

a^22 = a^16 * a^4 * a^2

       43210
n=22 = 10110

F(n) = F(2)* A^(n-2)

1 1 2 3 5 8 13 21 34 55
*/

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

int a[3][3], p[3][3], b[3][3], n;

/// C = A x B
void Produs(int a[3][3], int b[3][3], int c[3][3])
{
    int i, j;
    for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++)
    {
        c[i][j]= (1LL * a[i][1] * b[1][j]
                + 1LL * a[i][2]*b[2][j]) % P;
    }
}

/// A = B
void Copie(int a[3][3], int b[3][3])
{
    a[1][1] = b[1][1];
    a[1][2] = b[1][2];
    a[2][1] = b[2][1];
    a[2][2] = b[2][2];
}

/// a^n
void LogP(int n)
{
    p[1][1] = p[2][2] = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            Produs(p, a, b);
            Copie(p, b);
        }
        n /= 2;
        Produs(a, a, b);
        Copie(a, b);
    }
}

int main()
{
    fin >> n;
    if (n == 0)
    {
        fout << "0";
        fout.close();
        return 0;
    }

    a[1][1] = 0;
    a[1][2] = a[2][1] = a[2][2] = 1;
    LogP(n - 2);
    fout << (p[1][2] + p[2][2]) % P << "\n";
    fout.close();
    return 0;
}