#include <bits/stdc++.h>
#define N 2
#define M 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long a[N][N],b[N][N],sol[N][N],n;
void inmultire(long long a[N][N], long long b[N][N])
{
    int c[26][26],i,j,k;
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
        {
            c[i][j]=0;
            for(k=0; k<N; k++) {c[i][j]+=((a[i][k]%M)*(b[k][j]%M))%M;
            c[i][j]=c[i][j]%M;
            }
        }
    for(i=0; i<N; i++)
        for(j=0; j<N; j++) a[i][j]=c[i][j];
}
int main()
{
    a[0][0]=0;
    a[0][1]=1;
    b[0][1]=b[1][0]=b[1][1]=1;
    f>>n;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            if(i==j) sol[i][j]=1;
    }
    while(n)
    {
        if(n%2==1) inmultire(sol,b),n--;
        else inmultire(b,b),n/=2;
    }
    inmultire(a,sol);
    g<<a[0][0];
    return 0;
}