#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;

const int MOD = 666013;

int sol[2][2],b[2][2],aux[2][2],aux2[2][2];

void mult(int A[][2], int B[][2], int C[][2]){
    int i,j,k;
    for(i = 0;i < 2;i++){
        for(j = 0;j < 2;j++){
            for(k = 0;k < 2;k++){
                C[i][j] = (0LL + C[i][j] + 1LL*A[i][k]*B[k][j])%MOD;
            }
        }
    }
}


void lgput(int sol[][2], int e){
    int i,j;
    sol[0][0] = sol[1][1] = 1;
    b[0][1] = b[1][0] = b[1][1] = 1;
    while(e){
        if(e&1){
            for(i = 0;i < 2;i++){
                for(j = 0;j < 2;j++){
                    aux[i][j] = sol[i][j];
                    sol[i][j] = 0;
                }
            }
            mult(aux, b, sol);
        }
        for(i = 0;i < 2;i++){
            for(j = 0;j < 2;j++){
                aux[i][j] = b[i][j];
                aux2[i][j] = b[i][j];
                b[i][j] = 0;
            }
        }
        mult(aux, aux2, b);
        e >>= 1;
    }
}

int main()
{
    int t,n,k;
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    scanf("%d",&n);
    if(n == 0){
        printf("0");
        return 0;
    }
    lgput(sol,n-1);
    printf("%d",sol[1][1]);
    return 0;
}