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

#define MOD 666013

using namespace std;

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

int result(int x)
{
    pair<pair<int,int>,pair<int,int> > z;
    z = Z;
    x--;
    while( x )
    {
        if(x%2 == 0)
        {
            x/=2;
            z.first.first = (z.first.first * z.first.first)%MOD +(z.first.second * z.second.first)%MOD,
            z.first.second = (z.first.first * z.first.second)%MOD + (z.first.second * z.second.second)%MOD,
            z.second.first = (z.second.first*z.first.first)%MOD + (z.second.second * z.second.first)%MOD ,
            z.second.second = (z.second.first * z.first.second)%MOD + (z.second.second * z.second.second)%MOD;
        }
        else
            z.first.first = z.first.second,
            z.first.second = (z.first.first +z.first.second)%MOD,
            z.second.first = z.second.second,
            z.second.second = (z.second.first + z.second.second)%MOD,
            x--;
    }
    return (z.first.second + z.second.second)%MOD;
}


int main()
{
    freopen("kfib.in","r",stdin);
    //freopen("kfib.out","w",stdout);
    scanf("%d ",&n);
    solve();
    if(n==1 || n==2)
        printf("1");
    else
        printf("%d ",result(n-1));
    return 0;
}