#include<bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct matrice
{
    long long a[3][3];
};
matrice mat[32];
const int K=666013;
void afis(matrice x)
{
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
            cout<<x.a[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            mat[0].a[i][j]=1;
    mat[0].a[1][1]=0;
    for(int i=1;i<=31;i++)
    {
        matrice a=mat[i-1],b=mat[i-1],c;
        c.a[1][1]=(a.a[1][1]*b.a[1][1]+a.a[1][2]*b.a[2][1])%K;
        c.a[1][2]=(a.a[1][1]*b.a[1][2]+a.a[1][2]*b.a[2][2])%K;
        c.a[2][1]=(a.a[2][1]*b.a[1][1]+a.a[2][2]*b.a[2][1])%K;
        c.a[2][2]=(a.a[2][1]*b.a[1][2]+a.a[2][2]*b.a[2][2])%K;
        mat[i]=c;
    }
    afis(mat[2]);
    int k;
    fin>>k;
    if(k<=1)
        fout<<k;
    else
    {
        matrice x;
        x.a[1][1]=x.a[2][2]=1;
        x.a[1][2]=x.a[2][1]=0;
        long long nr=k-1;
        for(int i=0;i<=30;i++)
        {
            if(((1<<i)&nr)!=0)
            {
                matrice a=mat[i],b=x,c;
                c.a[1][1]=(a.a[1][1]*b.a[1][1]+a.a[1][2]*b.a[2][1])%K;
                c.a[1][2]=(a.a[1][1]*b.a[1][2]+a.a[1][2]*b.a[2][2])%K;
                c.a[2][1]=(a.a[2][1]*b.a[1][1]+a.a[2][2]*b.a[2][1])%K;
                c.a[2][2]=(a.a[2][1]*b.a[1][2]+a.a[2][2]*b.a[2][2])%K;
                x=c;
            }
        }
        fout<<x.a[2][2];

    }
}