#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 120010
#define mod 1999999973
#define eps 1e-12
using namespace std;
int i,j,n,x[2][2],sol[2][2];
int up1(int b[2][2],int c[2][2])
{
    int i,j,k,r[2][2]={0};
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
        for (k=0;k<=1;k++)
        r[i][j]=(r[i][j]+b[i][k]*1LL*c[k][j])%666013;
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
        sol[i][j]=r[i][j];
}
int up2(int b[2][2],int c[2][2])
{
    int i,j,k,r[2][2]={0};
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
        for (k=0;k<=1;k++)
        r[i][j]=(r[i][j]+b[i][k]*1LL*c[k][j])%666013;
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
        x[i][j]=r[i][j];
}
int main() {
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%d",&n);
x[0][1]=1; x[1][0]=1; x[1][1]=1;
sol[0][1]=1; sol[1][0]=1; sol[1][1]=1;
while (n>0) {
    if (n%2==1) up1(sol,x);
    up2(x,x);
    n=n/2;
}
printf("%d",sol[0][0]);
return 0;
}