#include<fstream>
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<queue>
#define f cin
#define g cout
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define inf (1<<30)
#define base 256
#define ba 255
#define N 5
#define EPS 1e-12
#define mod  666013
#define inu "kfib.in"
#define outu "kfib.out"
using namespace std;
ifstream f(inu);
ofstream g(outu);
//int dx[]={0,0,0,1,-1};
//int dy[]={0,1,-1,0,0};
int A[N][N],B[N][N],M[N][N],n;
long long val;
int main ()
{
    f>>n;
    if(!n)
    {
        g<<"0";
        return 0;
    }
    if(n==1)
    {
        g<<"1";
        return 0;
    }
    n--;
    A[1][1]=1; A[1][2]=1; A[2][1]=1;
    M[1][1]=1; M[1][2]=1; M[2][1]=1;
    while(n)
    {
        if(n&1)
        {
            FOR(i,1,2)
            FOR(j,1,2)
            {
            val=0;
            FOR(k,1,2)
            {
                val+=1LL*M[i][k]*A[k][j];
            }
            val%=mod;
            B[i][j]=val;
            }
            FOR(i,1,2)
            FOR(j,1,2)
            M[i][j]=B[i][j];
        }
        FOR(i,1,2)
        FOR(j,1,2)
        {
            val=0;
            FOR(k,1,2)
            {
                val+=1LL*A[i][k]*A[k][j];
            }
            val%=mod;
            B[i][j]=val;
        }
        FOR(i,1,2)
        FOR(j,1,2)
        A[i][j]=B[i][j];
        n>>=1;
    }
    g<<M[1][2];
    return 0;
}