#include <iostream>
#include<stdio.h>
using namespace std;
#include<fstream>

long long a[2][2], b[2][2], c[2][2];;

void prod_matr(long long c[2][2])
    {
        int x,y,z,t;
        x=b[0][0];
        y=b[0][1];
        z=b[1][0];
        t=b[1][1];
        b[0][0]=(c[0][0]*x+c[0][1]*z)%666013;
        b[0][1]=(c[0][0]*y+c[0][1]*t)%666013;
        b[1][0]=(c[1][0]*x+c[1][1]*z)%666013;
        b[1][1]=(c[1][0]*y+c[1][1]*t)%666013;
    }

void expo(int n)
    {
        if (n>=2)
            {
                expo(n/2);
                if (n%2==0)
                    {
                        c[0][0]=b[0][0];
                        c[0][1]=b[0][1];
                        c[1][0]=b[1][0];
                        c[1][1]=b[1][1]; prod_matr(c);
                    }
                else
                {
                    c[0][0]=b[0][0];
                        c[0][1]=b[0][1];
                        c[1][0]=b[1][0];
                        c[1][1]=b[1][1]; prod_matr(c);
                    prod_matr(a);
                }
            }
    }


int main()
{
    int n;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    b[0][0]=a[0][0]=1;
    b[0][1]=a[0][1]=1;
    b[1][0]=a[1][0]=1;
    b[1][1]=a[1][1]=0;
    expo(n-1);
    g<<b[0][0];

    return 0;
}