#include <fstream>
#define MOD 666013

using namespace std;

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

int n;

struct matrice
{
    long long int a11, a12, a21, a22;
} fib, fibn;

void initializare();
matrice putere_logaritmic(int k);
matrice inmultire_matrice(matrice A, matrice B);

//      | 1  1 |         | f(n+1)  f(n)   |
// fib= |      |  fib^n= |                |
//      | 1  0 |         | f(n)    f(n-1) |

int main()
{
    fin>>n;
    initializare();
    fibn=putere_logaritmic(n-1);
    fout<<fibn.a11<<'\n';
    return 0;
}

void initializare()
{
    fib.a11=1; fib.a12=1;
    fib.a21=1; fib.a22=0;
}

matrice putere_logaritmic(int k)
{
    if(k==1) return fib;

    matrice aux=putere_logaritmic(k/2);
    matrice rez=inmultire_matrice(aux, aux);
    if(k%2==1) rez=inmultire_matrice(rez, fib);

    return rez;
}

matrice inmultire_matrice(matrice A, matrice B)
{
    matrice rez;

    A.a11%=MOD; A.a12%=MOD; A.a21%=MOD; A.a22%=MOD;
    B.a11%=MOD; B.a12%=MOD; B.a21%=MOD; B.a22%=MOD;

    rez.a11=((A.a11*B.a11)%MOD+(A.a12*B.a21)%MOD)%MOD;
    rez.a12=((A.a11*B.a12)%MOD+(A.a12*B.a22)%MOD)%MOD;
    rez.a21=((A.a21*B.a11)%MOD+(A.a22*B.a21)%MOD)%MOD;
    rez.a22=((A.a21*B.a12)%MOD+(A.a22*B.a22)%MOD)%MOD;

    return rez;
}