#include <bits/stdc++.h>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int dim=2,mod=666013;
int n;
struct matrix
{
    int v[dim][dim];
    matrix()
    {
        memset(v,0,sizeof(v));
    }
    void unit()
    {
        for(int i=0; i<dim; i++) v[i][i]=1;
    } matrix operator *(matrix a)
    {
        matrix rez;
        for(int i=0; i<dim; ++i)for(int j=0; j<dim; ++j)for(int y=0; y<dim; ++y)rez.v[i][j]=(rez.v[i][j]+1LL*v[i][y]*a.v[y][j])%mod;
        return rez;
    }
}a,b,c,p;
matrix pow(matrix a,int power)
{
    matrix p;
    p.unit();
    for(int i=1; i<=power; i<<=1)
    {
        if(power&i) p=p*a;
        a=a*a;
    }
    return p;
}
int main()
{
    in>>n;
    a.v[0][0]=a.v[0][1]=a.v[1][0]=1;b.v[0][0]=b.v[0][1]=1;
    p=pow(a,n-1);
    c=b*p;
    out<<c.v[0][1];
    return 0;
}