#include <iostream>
#include <fstream>

using namespace std;

const int MOD = 666013;

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

void inmultire(long long a[3][3], long long b[3][3])
{
    int n, m;
    n = m = 2;
    int nq, mq;
    nq = mq = 0;
    long long c[3][3];
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < m; j++)
        {
            int sum = 0;
            for(int k = 0; k < n; k++)
            {
                sum += ((a[j][k])%MOD * (b[k][i])%MOD)%MOD;
            }
            c[mq++][nq] = sum;
            if(mq%n == 0)
            {
                nq++;
                mq = 0;
            }
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            a[i][j] = c[i][j];
}

long long putere(long long p)
{
    long long rez[3][3], fact[3][3];
    rez[0][0] = fact[0][0] = 0;
    rez[0][1] = fact[0][1] = 1;
    rez[1][0] = fact[1][0] = 1;
    rez[1][1] = fact[1][1] = 1;
    for(int bit = 0; p >> bit; bit++)
    {
        if((p>>bit) & 1)
        {
            inmultire(rez, fact);
        }
        inmultire(fact, fact);
    }
    return rez[0][1];
}

int main()
{
    int k;
    fin >> k;
    if(!k)
    {
        fout << k;
        return 0;
    }
    fout << putere(k-1)%MOD;
    return 0;
}