#include <iostream>
#include <fstream>
#define c 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long a11=0,a12=1,a21=1,a22=1,k;
bool b;
void inmultire (long long int &a11,long long int &a12,long long int &a21,long long int &a22)
{
    long long int b11,b12,b21,b22;

    b11=a11*a11+a12*a21;
    b22=a21*a12+a22*a22;
    b12=a11*a12+a12*a22;
    b21=a21*a11+a22*a21;
    b11%=c;
    b12%=c;
    b21%=c;
    b22%=c;

  a11=b11;a21=b21;a12=b12;a22=b22;
}

void putere(int k,long long int &a11,long long int &a12,long long int &a21,long long int &a22)
{
    long long int b11=0,b12=1,b21=1,b22=1;
    while(k>0)
    {
        if(k%2){
        long long int c11,c22,c12,c21;
        c11=b11*a11+b12*a21;
        c12=b11*a12+b12*a22;
        c21=b21*a11+b22*a21;
        c22=b21*a12+b22*a22;
        c11%=c;c12%=c;c21%=c;c22%=c;
        b11=c11;b12=c12;b21=c21;b22=c22;
        k--;
        }
      inmultire (a11,a12,a21,a22);
      k/=2;
    }
   a11=b11;a21=b21;a12=b12;a22=b22;
}
int main()
{
f>>k;
k-=2;
putere(k-1,a11,a12,a21,a22);
//cout<<a11<<" "<<a12<<'\n'<<a21<<" "<<a22;

g<<a12+a22;
}