#include <iostream>
#include <fstream>
#include <math.h>

#define MOD 666013

using namespace std;

pair<pair<int,int>,pair<int,int> > Z,I,S;
int n;
void solve()
{
    Z.first.first = 0 ;
    Z.first.second = 1 ;
    Z.second.first = 1;
    Z.second.second = 1;
    I.first.first=1;
    I.first.second=0;
    I.second.first=0;
    I.second.second=1;
}

pair<pair<int,int>,pair<int,int> >produs(pair<pair<int,int>,pair<int,int> > A,pair<pair<int,int>,pair<int,int> > B)
{
    pair<pair<int,int>,pair<int,int> > C;
    C.first.first = ((A.first.first * B.first.first)%MOD + (A.first.second * B.second.first)%MOD)%MOD;
    C.first.second = ((A.first.first * B.first.second)%MOD + (A.first.second * B.second.second)%MOD)%MOD;
    C.second.first = ((A.first.second * B.first.first)%MOD + (A.second.second * B.second.first)%MOD)%MOD;
    C.second.second = ((A.first.second * B.first.second)%MOD + (A.second.second * B.second.second)%MOD)%MOD;
    return C;
}

pair<pair<int,int>,pair<int,int> > result(pair<pair<int,int>,pair<int,int> > A, int k)
{
    if(k==0)
        return produs(A,I);
    if(k%2==0)
        return result(produs(A,A),k/2);
    else
        return produs(result(A,k-1),Z);
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d ",&n);
    solve();
    if(n==1 || n==2)
        printf("1");
    else
        {
            S=result(Z,n-3);
            printf("%d\n",(S.first.second+S.second.second)%MOD);
        }
    return 0;
}