#include <bits/stdc++.h>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

typedef tuple<int,int ,int> matr;
int n;
const int M=666013;

matr operator *(matr a,matr b)
{
    int x1,y1,z1,x2,y2,z2;
    tie(x1,y1,z1)=a;
    tie(x2,y2,z2)=b;
    return make_tuple( (1LL*x1*x2 +1LL*y1*y2)%M,(1LL*x1*y2+1LL*y1*z2)%M,(1LL*y1*y2+1LL*z1*z2)%M);
}

matr fibonacci(int b)
{
    if(b==0)return make_tuple(1,0,1);
    matr c=fibonacci(b/2);
    c=c*c;
    if(b&1)
        c=make_tuple(1,1,0)*c;
    return c;
}

int main()
{
    f>>n;
    g<<get<1>(fibonacci(n));
    return 0;
}