#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef int matrix[2][2];
void mult(matrix a,matrix b)
{
    matrix c= {{0,0},{0,0}};
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
            {
                c[i][j]=(1LL*a[i][k]*b[k][j]+c[i][j])%666013;
            }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j]=c[i][j];
}
void expo(matrix a,long long b)
{
    matrix r= {{1,0},{0,1}};
    while(b!=0)
    {
        if(b%2)
            mult(r,a);
        mult(a,a);
        b/=2;
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a[i][j]=r[i][j];
}
int main()
{
    long long k;
    matrix p= {{0,1},{1,1}};
    f>>k;
    expo(p,k);
    g<<p[1][0]%666013;
    return 0;
}