#include<fstream>
using namespace std;
ifstream f ("kfib.in");
ofstream g ("kfib.out");
long long n,x,y,z,t,a,b,c,d,auxa,auxb,auxc,auxd;
int main()
{
    f>>n;
    if(n==0){
        g<<0;
        return 0;
    }
    if(n==1){
        g<<1;
        return 0;
    }
    x=0;
    y=1;
    z=1;
    t=1;
    --n;
    a=1;
    b=0;
    c=0;
    d=1;
    while(n>0){
        if(n%2==1){
            --n;
            auxa=(a*x+b*z)%666013;
            auxb=(a*y+b*t)%666013;
            auxc=(c*x+d*z)%666013;
            auxd=(c*y+d*t)%666013;
            a=auxa;
            b=auxb;
            c=auxc;
            d=auxd;
        }
        else{
        auxa=(x*x+y*z)%666013;
        auxb=(x*y+y*t)%666013;
        auxc=(z*x+t*z)%666013;
        auxd=(z*y+t*t)%666013;
        x=auxa;
        y=auxb;
        z=auxc;
        t=auxd;
        n/=2;
        }
    }
    g<<d;
    return 0;
}