#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(matr a,int b)
{
    if(b==0)return make_tuple(1,0,1);
    if(!(b%2))
    {
        matr c=fibonacci(a,b/2);
        return c*c;
    }
    return a*fibonacci(a,b-1);
}

int main()
{
    matr a=make_tuple(1,1,0);
    f>>n;
    a=fibonacci(a,n);
    g<<get<1>(a);
    return 0;
}