#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;

int n;
int Z[3][3],SOL[3][3];

void multiply(int A[3][3],int B[3][3],int C[3][3])
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%mod;
}
void lg_power(int P,int M[][3])
{
    int C[3][3],aux[3][3];
    memcpy(C,Z,sizeof(Z));
    M[0][0]=M[1][1]=1;
    for(int i=0;1<<i<=P;i++)
    {
        if(P & (1<<i))
        {
                memset(aux,0,sizeof(aux));
                multiply(M,C,aux);
                memcpy(M,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        multiply(C,C,aux);
        memcpy(C,aux,sizeof(aux));
    }
}
int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    scanf("%d", &n);
    Z[0][0] = 0; Z[0][1] = 1; Z[1][0] = 1; Z[1][1] = 1;
    lg_power(n - 1, SOL);
    printf("%d\n", SOL[1][1]);

    return 0;
}