#include <iostream>
#include <fstream>

using namespace std;

long long a[10], b[10], aux, aux1, aux2, aux3, aux4;

void putere()
{
    aux1=b[1];
    aux2=b[2];
    aux3=b[3];
    aux4=b[4];
    b[1]=(aux1*aux1+aux2*aux3)%666013;
    b[2]=(aux1*aux2+aux2*aux4)%666013;
    b[3]=(aux3*aux1+aux4*aux3)%666013;
    b[4]=(aux3*aux2+aux4*aux4)%666013;
}

void inmultire()
{
    aux1=a[1];
    aux2=a[2];
    aux3=a[3];
    aux4=a[4];
    a[1]=(aux1*b[1]+aux2*b[3])%666013;
    a[2]=(aux1*b[2]+aux2*b[4])%666013;
    a[3]=(aux3*b[1]+aux4*b[3])%666013;
    a[4]=(aux3*b[2]+aux4*b[4])%666013;
}

int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    long long n, p;
    fin >> n;
    a[1]=0;
    a[2]=a[3]=a[4]=1;
    b[1]=0;
    b[2]=b[3]=b[4]=1;
    while (n)
    {
        if (n%2)
            inmultire();
        putere();
        n/=2;
    }
    fout << a[1];
    return 0;
}