#include <iostream>
#include <stdio.h>
#include <strings.h>
#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

int n,i,j;
int a[3][3];
int b[3][3];
int v[3][3];

void init(int a[3][3]){
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;

}

void inmultire(int a[3][3],int b[3][3]){
    int i,j,k,aux[3][3];

    memset(aux,0,sizeof(aux));

    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            for(k=1;k<=2;k++)
                aux[i][j]=(aux[i][j]+1LL*b[i][k]*a[k][j]%MOD)%MOD;

    memcpy(a,aux,sizeof(aux));

}

void exponentiere(){
    int i;

    for(i=0;(1<<i)<=n;i++){
        if((1<<i) & n){
            inmultire(v,b);
        }

        inmultire(b,b);

    }
}

int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);

    scanf("%d",&n);


    init(a);
    init(b);
    init(v);

    exponentiere();


    /*for(i=1;i<=2;i++){
        for(j=1;j<=2;j++)
            printf("%d ",v[i][j]);
        printf("\n");
    }*/

    printf("%d",v[2][2]);

    return 0;
}