#include <iostream>
#include <fstream>
#include <algorithm>
#define MOD 666013
#define dim 2
#define kmax 1000000000
#define long long long
using namespace std;
int k;
class matrice
{
    public:
        long a[dim][dim];
        matrice inmultire( matrice a, matrice b)
        {
            matrice c;
            int i,j;
            for (i = 0 ; i < dim ; ++i)
                for (j = 0 ; j < dim ; ++j){
                    long sum = 0;
                    for (int r=0 ; r < dim ; ++r)
                        sum += a.a[i][r]*b.a[r][j];
                    c.a[i][j] = sum;
                }
            return c;
        }

};
matrice inmultireModulo( matrice a, matrice b, int modulo)
    {
        matrice c;
        int i,j;
        for (i = 0 ; i < dim ; ++i)
            for (j = 0 ; j < dim ; ++j){
                long sum = 0;
                for (int r=0 ; r < dim ; ++r)
                    sum = (sum + a.a[i][r]*b.a[r][j]) % modulo;
                c.a[i][j] = sum;
            }
        return c;
    }
void seteaza( matrice a[])
{
    a[0].a[0][0] = 1;
    a[0].a[0][1] = 0;
    a[0].a[1][0] = 0;
    a[0].a[1][1] = 1;

    a[1].a[0][0] = 0;
    a[1].a[0][1] = 1;
    a[1].a[1][0] = 1;
    a[1].a[1][1] = 1;
}

int max_exponent=0;
const int dim_max = 32;

void exponenti(int nr, int exp[])
{
    if (!nr) return ;
    exponenti(nr/2, exp);
    exp[max_exponent++] = nr%2;
}
int kfib(int n)
{

    int exp[dim_max] = {0};
    n--;
    exponenti(n,exp);
    reverse(exp,exp+max_exponent);
    int i;
    matrice a[max_exponent+1];
    seteaza(a);
    for (i = 2 ; i<= max_exponent ; i++)
        a[i] = inmultireModulo(a[i-1],a[i-1],MOD);
    matrice sol = a[0];
    for (i = 0; i < max_exponent ; i++)
        if( exp[i] )
            sol = inmultireModulo(sol, a[i+1], MOD);
    return sol.a[1][1];
}
int main()
{
    fstream f,g;
    f.open("kfib.in",ios::in);
    g.open("kfib.out",ios::out);
    f>>k;
    g<<kfib(k);
    f.close();
    g.close();
    return 0;
}