#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

void copiere(long long a[][2], long long b[][2])
{
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j] = b[i][j];
}

void matrix_power(long long a[2][2], long long b[2][2], long long c[2][2])
{
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
        {
            int s=0;
            for(int k=0; k<2; k++)
                s += ((a[i][k]%MOD) * (b[k][j]%MOD)) % MOD;
            c[i][j] = s % MOD;
        }
}

long long putere(long long n, long long z[2][2], long long sol[2][2])
{
    long long partial[2][2];
    while(n!=0)
    {
        if(n%2 == 1)
        {
            matrix_power(z,sol,partial);
            copiere(sol,partial);
        }
        matrix_power(z,z,partial);
        copiere(z,partial);
        n /= 2;
    }
    return sol[0][1];
}

int main()
{
    long long k; f>>k;
    long long z[2][2], sol[2][2];
    z[0][0] = 0, z[0][1] = z[1][0] = z[1][1] = 1;
    for(int i=0; i<2; i++)
        for(int j=0;j<2;j++)
            sol[i][j] = 1;
    g<<putere(k-1,z,sol);
}