#include <fstream>
#define NRM 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int k,m[2][2]={0,1,1,1},i,j;
long long fib[2][2],aux[2][2];

void put(int p);

int main()
{
    f>>k;
    k--;
    put(k);
    g<<fib[1][1]<<'\n';
    f.close();
    g.close();
    return 0;
}

void put(int p){
    if(p==2){
        fib[0][0]=fib[0][1]=fib[1][0]=1;
        fib[1][1]=2;
        return;}
    if(p==1){
        fib[0][0]=0;
        fib[0][1]=fib[1][0]=fib[1][1]=1;
        return;}
    put(p/2);
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            aux[i][j]=(fib[i][0]*fib[0][j]+fib[i][1]*fib[1][j])%NRM;
    for(i=0;i<=1;i++)
        for(j=0;j<=1;j++)
            fib[i][j]=aux[i][j];
    if(p%2){
        for(i=0;i<=1;i++)
            for(j=0;j<=1;j++)
                aux[i][j]=(fib[i][0]*m[0][j]+fib[i][1]*m[1][j])%NRM;
        for(i=0;i<=1;i++)
            for(j=0;j<=1;j++)
                fib[i][j]=aux[i][j];}}