#include <iostream>
#include <bits/stdc++.h>
#define VMAX 2
#define int long long int
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

struct matrice{
int n;
int a[VMAX][VMAX];
};

const int mod = 666013;


void unitate(matrice& a,int n)
{
    a.n=n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)
                a.a[i][j]=1;
            else
               a.a[i][j]=0;
        }
    }
}

matrice produs(matrice a, matrice b)
{
    matrice c;
    c.n=a.n;
    for(int i=0;i<a.n;i++)
    {
        for(int j=0;j<a.n;j++)
        {
            c.a[i][j]=0;
            for(int k=0;k<a.n;k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            }
        }
    }
    return c;
}


matrice prodm(matrice x, int exp)
{
    matrice p;
    unitate(p,x.n);

    while(exp)
    {
        if(exp%2)
        {
            p=produs(p,x);
            exp--;
        }
        else
        {
            x=produs(x,x);
            exp/=2;
        }
    }
    return p;

}

signed main()
{
    int n;
    matrice x;
    fin>>n;
    x.n=2;
    x.a[0][0]=0;
    x.a[0][1]=x.a[1][1]=x.a[1][0]=1;
    x=prodm(x,n);
    fout<<x.a[0][1];
    return 0;
}