#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;

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

int log_pow(int n)
{
    long long a=0, b=1, c=1, d=1;
    long long R1=0, R2=1, R3=1, R4=1;

    while(n)
    {
        if(n%2!=0)
        {
            long long RR1=R1, RR2=R2, RR3=R3, RR4=R4;

            R1=((RR1*a)%MOD+(RR2*c)%MOD)%MOD;
            R2=((RR1*b)%MOD+(RR2*d)%MOD)%MOD;

            R3=((RR3*a)%MOD+(RR4*c)%MOD)%MOD;
            R4=((RR3*b)%MOD+(RR4*d)%MOD)%MOD;
        }

        long long aa=a, bb=b, cc=c, dd=d;

        a=((aa*aa)%MOD+(bb*cc)%MOD)%MOD;
        b=((bb%MOD)*((aa+dd)%MOD))%MOD;

        c=((cc%MOD)*((aa+dd)%MOD))%MOD;
        d=((dd*dd)%MOD+(bb*cc)%MOD)%MOD;

        n/=2;
    }

    return R4;
}

int main()
{
    int n;
    fin >> n;

    fout << log_pow(n-2);
    return 0;
}