#include <stdio.h>
#define D 666013
using namespace std;

void read_(int &nr) {
     scanf("%d", &nr);     
}

typedef struct matr_2x2 {
     long long int e11, e12, e21, e22;   
} matr_2x2;

typedef struct matr_1x2 {
     long long int e11, e12;        
} matr_1x2;

matr_2x2 modulo_D_2x2(matr_2x2 A) {
     A.e11 = A.e11 % D;
     A.e21 = A.e21 % D;
     A.e12 = A.e12 % D;
     A.e22 = A.e22 % D;     
     return A;    
}

matr_1x2 modulo_D_1x2(matr_1x2 A) {
     A.e11 = A.e11 % D;
     A.e12 = A.e12 % D;
     return A;         
}

matr_1x2 make_matr_1x2(int a, int b) {
     matr_1x2 M;
     M.e11 = a;
     M.e12 = b;
     return M;         
}

matr_2x2 make_matr_2x2(int a1, int a2, int b1, int b2) {
     matr_2x2 M;
     M.e11 = a1;
     M.e12 = a2;
     M.e21 = b1;
     M.e22 = b2;
     return M;         
}

matr_1x2 prod_fin(matr_1x2 F, matr_2x2 A) {
     matr_1x2 R;
     R.e11 = F.e11 * A.e11 + F.e12 * A.e21;
     R.e12 = F.e11 * A.e12 + F.e12 * A.e22;
     return modulo_D_1x2(R);         
}

matr_2x2 prod(matr_2x2 A, matr_2x2 B) {
     matr_2x2 R;
     R.e11 = A.e11 * B.e11 + A.e12 * B.e21;
     R.e12 = A.e11 * B.e12 + A.e12 * B.e22;
     R.e21 = A.e21 * B.e11 + A.e22 * B.e21;
     R.e22 = A.e21 * B.e12 + A.e22 * B.e22;
     return modulo_D_2x2(R);
}

matr_2x2 power(matr_2x2 A, int e) {
     if (e == 0) {
         return (make_matr_2x2(1,0,0,1));      
     } else if (e == 1) {
         return modulo_D_2x2(A);            
     }
     
     if (e % 2 == 1) {
         return (prod(prod(power(A, e/2), power(A, e/2)), A));   
     } 
     return (prod(power(A, e/2), power(A, e/2)));
}

void print_matr_2x2(matr_2x2 A) {
     printf("%d  |  %d\n--------\n%d  |  %d\n", A.e11, A.e12, A.e21, A.e22);     
}

void fibb(int n) {
     matr_1x2 Fin;
     matr_1x2 F1 = make_matr_1x2(0, 1);
     matr_2x2 Z = make_matr_2x2(0, 1, 1, 1);
     Fin = prod_fin(F1, power(Z, n - 1));      
     printf("%lld", Fin.e12);    
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    
    int nr;
    read_(nr);
    fibb(nr);
    return 0;
}