#include <bits/stdc++.h>
using namespace std;
#define ll long long

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

const int modulo=666013;

ll F[2][2] = {{0,0},
              {0,1}};
ll M[2][2] = {{0,1},
              {1,1}};

void inmultire(ll A[2][2], ll B[2][2])
{
    ll temp[2][2];

    temp[0][0]=(A[0][0]*B[0][0] + A[0][1]*B[1][0])%modulo;
    temp[0][1]=(A[0][0]*B[0][1] + A[0][1]*B[1][1])%modulo;
    temp[1][0]=(A[1][0]*B[0][0] + A[1][1]*B[1][0])%modulo;
    temp[1][1]=(A[1][0]*B[0][1] + A[1][1]*B[1][1])%modulo;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++) A[i][j]=temp[i][j];
}

void exp(int n)
{
    while(n)
    {
        if(n%2==1) inmultire(F,M);
        n/=2;
        inmultire(M,M);
    }
}

int main()
{
    int n; in>>n;

    exp(n-1);
    out<<F[1][1];
    return 0;
}