#include <iostream>
#include <fstream>
using namespace std;

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

struct mat{
    long long e1,e2,e3,e4;
};

mat inm(mat a,mat b)
{
    mat aux;
    aux.e1=(a.e1*b.e1%666013+a.e2*b.e3%666013)%666013;
    aux.e2=(a.e1*b.e2%666013+a.e2*b.e4%666013)%666013;
    aux.e3=(a.e3*b.e1%666013+a.e4*b.e3%666013)%666013;
    aux.e4=(a.e3*b.e2%666013+a.e4*b.e4%666013)%666013;
    return aux;
}

int main()
{
    mat a,aux;
    int n;
    fin>>n;
    n--;
    a.e1=0;
    a.e2=1;
    a.e3=1;
    a.e4=1;
    aux.e1=1;
    aux.e2=0;
    aux.e3=0;
    aux.e4=1;
    while(n>0)
    {
        if(n%2==1)
        {
            n--;
            aux=inm(aux,a);
        }
        n=n>>1;
        a=inm(a,a);
    }
    fout<<aux.e4;
    return 0;
}