#include <bits/stdc++.h>
#define R 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int K;

typedef long long unsigned ull;

int main()
{
    ull aux[2][2];
    ull A[2][2]={0,1,1,1};
    ull Aprim[2][2]={1,0,0,1};
    ull B[2][2]={0,1,1,1};
    fin>>K;
    K-=1;
    while(K)
    {
        if(K%2==1)
        {
            aux[0][0]=Aprim[0][0]*A[0][0]%R+A[1][0]*Aprim[0][1]%R;
            aux[0][1]=Aprim[0][0]*A[0][1]%R+Aprim[0][1]*A[1][1]%R;
            aux[1][0]=aux[0][1]%R;
            aux[1][1]=Aprim[1][0]*A[0][1]%R+Aprim[1][1]*A[1][1]%R;
            for(int k=0;k<=1;k++)
                for(int j=0;j<=1;j++)Aprim[k][j]=aux[k][j]%R;
            K--;
        }else{
            aux[0][0]=A[0][0]*A[0][0]%R+A[0][1]*A[1][0]%R;
            aux[0][1]=A[0][0]*A[0][1]%R+A[0][1]*A[1][1]%R;
            aux[1][0]=aux[0][1]%R;
            aux[1][1]=A[1][0]*A[0][1]%R+A[1][1]*A[1][1]%R;
            for(int k=0;k<=1;k++)
                for(int j=0;j<=1;j++)A[k][j]=aux[k][j]%R;
            K/=2;
        }
    }
    fout<<Aprim[1][1]%R;
    return 0;
}