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

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

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

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) {
     long long F1, F2;
     F1 = (F.e11 * A.e11 + F.e12 * A.e21) % D;
     F2 = (F.e11 * A.e12 + F.e12 * A.e22) % D;
     F.e11 = F1; F.e12 = F2;
     return F;         
}

matr_2x2 prod(matr_2x2 A, matr_2x2 B) {
     long long A1, A2, A3, A4;
     A1 = (A.e11 * B.e11 + A.e12 * B.e21) % D;
     A2 = (A.e11 * B.e12 + A.e12 * B.e22) % D;
     A3 = (A.e21 * B.e11 + A.e22 * B.e21) % D;
     A4 = (A.e21 * B.e12 + A.e22 * B.e22) % D;
     A.e11 = A1; A.e12 = A2; A.e21 = A3; A.e22 = A4;
     return A;
}

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

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;
    scanf("%d", &nr); 
    fibb(nr);
    return 0;
}