#include <bits/stdc++.h>
#define rest 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long f[2][2]={{0,1},{1,1}};
long long r[2][2]={{0,1},{1,1}};
int k;
int main()
{
    fin>>k;
    int i=0;
    k-=2;
    while(k>0)
    {
        if(k%2==0)
        {
            long long x=(f[0][0]*f[0][0]+f[0][1]*f[1][0])%rest;
            long long y=(f[0][0]*f[0][1]+f[0][1]*f[1][1])%rest;
            long long z=(f[1][0]*f[0][0]+f[1][1]*f[1][0])%rest;
            long long w=(f[1][0]*f[0][1]+f[1][1]*f[1][1])%rest;
            f[0][0]=x;
            f[0][1]=y;
            f[1][0]=z;
            f[1][1]=w;
            k/=2;
            continue;
        }
        i++;
            long long x=(r[0][0]*f[0][0]+r[0][1]*f[1][0])%rest;
            long long y=(r[0][0]*f[0][1]+r[0][1]*f[1][1])%rest;
            long long z=(r[1][0]*f[0][0]+r[1][1]*f[1][0])%rest;
            long long w=(r[1][0]*f[0][1]+r[1][1]*f[1][1])%rest;
            r[0][0]=x;
            r[0][1]=y;
            r[1][0]=z;
            r[1][1]=w;
            k--;
    }
    fout<<r[1][1];
    return 0;
}