#include <cstdio>

using namespace std;
#define mod 666013
struct mat{
    long long m[3][3];
};
mat a,an;
int n;
mat lg(int n)
{

   if(n==1) return a;
   mat b,c;
   b=lg(n/2);
   c.m[1][1]=(b.m[1][1]*b.m[1][1]%mod+b.m[1][2]*b.m[2][1])%mod;
   c.m[1][2]=(b.m[1][1]*b.m[1][2]%mod+b.m[1][2]*b.m[2][2])%mod;
   c.m[2][1]=(b.m[2][1]*b.m[1][1]+b.m[2][2]*b.m[2][1])%mod;
   c.m[2][2]=(b.m[2][1]*b.m[1][2]+b.m[2][2]*b.m[2][2])%mod;
   if(n%2==1)
    {
        b.m[1][1]=(c.m[1][1]*a.m[1][1]+c.m[1][2]*a.m[2][1])%mod;
        b.m[1][2]=(c.m[1][1]*a.m[1][2]+c.m[1][2]*a.m[2][2])%mod;
        b.m[2][1]=(c.m[2][1]*a.m[1][1]+c.m[2][2]*a.m[2][1])%mod;
        b.m[2][2]=(c.m[2][1]*a.m[1][2]+c.m[2][2]*a.m[2][2])%mod;
        return b;
    }
    return c;
}
int main()
{
   freopen("kfib.in","r",stdin);
   freopen("kfib.out","w",stdout);
   scanf("%d",&n);

   a.m[1][1]=a.m[2][1]=a.m[1][2]=1;
   an=lg(n-1);

   printf("%d\n",an.m[1][1]);
    return 0;
}