#include<bits/stdc++.h>
#define m 666013

using namespace std;

int k;

pair<pair<int,int>,pair<int,int>>inmultire(pair<pair<int,int>,pair<int,int>>A,pair<pair<int,int>,pair<int,int>>B)
{

    int a=A.first.first;
    int b=A.first.second;
    int c=A.second.first;
    int d=A.second.second;
    int e=B.first.first;
    int f=B.first.second;
    int g=B.second.first;
    int h=B.second.second;
    pair<pair<int,int>,pair<int,int>>r;
    r.first.first=(1LL*a*e%m+1LL*b*g%m)%m;
    r.second.second=(1LL*c*f%m+1LL*d*h%m)%m;
    r.first.second=(1LL*a*f%m+1LL*b*h%m)%m;
    r.second.first=(1LL*c*e%m+1LL*d*g%m)%m ;
    return r;

}
pair<pair<int,int>,pair<int,int>>puteri(pair<pair<int,int>,pair<int,int>>z,int k)
{
    pair<pair<int,int>,pair<int,int>>aux ;
    pair<pair<int,int>,pair<int,int>>rt ;

     rt.first.first=1;
     rt.first.second=0;
     rt.second.first=0;
     rt.second.second=1;
     while(k)
     {
        if(k%2==1)
        {
            aux=inmultire(rt,z);
            rt=aux;
        }
        aux=inmultire(z,z);
        z=aux;
        k=k/2;
     }
     return rt;
}

int main()
{

    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>k;
    pair<pair<int,int>,pair<int,int>>mat,fin;
    mat.first.first=0;
    mat.first.second=1;
    mat.second.second=1;
    mat.second.first=1;
    fin=puteri(mat,k-1);
    g<<(fin.first.first+fin.second.first)%m;
    return 0;


}