#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int nMax=1e5+5,MOD=666013;

ll t,n,m,k,x,y,z,a,b,c,d,cnt,ans,rez,sum,poz,st,dr;
ll F[3],A[3][3],C[3][3],B[3][3];
vector<array<int,5>>mo;
void mlt(ll d,ll A[3][3], ll B[3][3])
{
    for(int i = 1; i <=d; i++)
    {
        for(int j = 1; j <=d; j++)
        {
            C[i][j] = 0;
            for(int k = 1; k <=d; k++)
            {
                rez = C[i][j]+A[i][k]*B[k][j];
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%MOD;
            }
        }
    }
}
void fastPow(ll p)
{
    while(p)
    {
        if(p%2)
            p--,mlt(2,A,B),B[1][1]=C[1][1],B[1][2]=C[1][2],B[2][1]=C[2][1],B[2][2]=C[2][2];
        else
            p/=2,mlt(2,A,A),A[1][1]=C[1][1],A[1][2]=C[1][2],A[2][1]=C[2][1],A[2][2]=C[2][2];
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    fin>>n;
    A[1][1]=0,A[1][2]=1;
    A[2][1]=1,A[2][2]=1;
    B[1][1]=1,B[2][2]=1;
    F[1]=1;
    fastPow(n);
    fout<<(F[0]*B[1][1]+F[1]*B[1][2])%MOD;
}