#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;


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


int p;


void lgput()
{
    int a=0;
    int b=1;
    int c=1;
    int d=1;

    int ax=1;
    int bx=0;
    int cx=0;
    int dx=1;
    while(p)
    {
        if(p%2)
        {
            int aax=(1ll*ax*a+1ll*bx*c)%mod;
            int bbx=(1ll*ax*b+1ll*bx*d)%mod;
            int ccx=(1ll*cx*a+1ll*dx*c)%mod;
            int ddx=(1ll*cx*b+1ll*dx*d)%mod;
            ax=aax;
            bx=bbx;
            cx=ccx;
            dx=ddx;
            p--;
        }
        int aa=(1ll*a*a+1ll*b*c)%mod;
        int bb=(1ll*a*b+1ll*b*d)%mod;
        int cc=(1ll*c*a+1ll*d*c)%mod;
        int dd=(1ll*c*b+1ll*d*d)%mod;
        a=aa;
        b=bb;
        c=cc;
        d=dd;
        p/=2;
    }
    fout<<(bx+dx)%mod;
}


int main()
{
    fin>>p;
    if(p==1 || p==2 || p==3)
    {
        if(p==3) fout<<2;
        else fout<<1;
        return 0;
    }
    p-=2;
    lgput();
    return 0;
}