#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 kfib(int n)
{
    // puteri de ale lui 2
    const int dim_max = 32;
    long puteri[dim_max];
    puteri[0] = 1;
    int i;
    for (i = 1 ; i < dim_max ; i++)
        puteri[i] = puteri[i-1] * 2;

    // descompunem pe n
    n--;
    // ----------------
    int exp[dim_max] = {0};
    long * it;
    it = upper_bound(puteri, puteri + dim_max , n);
    it--;
    int max_exponent =  it-puteri;
    exp[max_exponent] = 1;
    n -= *it;
    while (n)
    {
        it = upper_bound(puteri, puteri + dim_max , n);
        it--;
        n -= *it;
        exp[ it-puteri ] = 1;
    }
    // a[i] = a[0]^ (2^(i-1) )
    max_exponent++;
    matrice a[max_exponent];
    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;
}