#include <iostream>
#include <cstdio>
 
#define MOD 666013
 
using namespace std;
 
long long a[3][3],f[3][3];
 
void mult(long long x[3][3],long long y[3][3])
{
    long long  a[3][3];
    a[1][1]=x[1][1]*y[1][1]%MOD+x[1][2]*y[2][1]%MOD;
    a[1][2]=x[1][1]*y[1][2]%MOD+x[1][2]*y[2][2]%MOD;
    a[2][1]=x[2][1]*y[1][1]%MOD+x[2][2]*y[2][1]%MOD;
    a[2][2]=x[2][1]*y[1][2]%MOD+x[2][2]*y[2][2]%MOD;
    x[1][1]=a[1][1]%MOD;
    x[1][2]=a[1][2]%MOD;
    x[2][1]=a[2][1]%MOD;
    x[2][2]=a[2][2]%MOD;
}
 
void put(long long n)
{
    if(n==1)
        return;
    put(n/2);
    mult(f,f);
    if(n%2)
        mult(f,a);
}
 
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    long long n;
    f[1][1]=f[1][2]=f[2][1]=a[1][1]=a[1][2]=a[2][1]=1;
    f[2][2]=a[2][2]=0;
    cin>>n;
    if(n==0)
        cout<<"0\n";
    else if(n==1||n==2)
        cout<<"1\n";
    else
 
    {put(n-1);
    cout<<f[1][1]<<"\n";}
    return 0;
}