#include <stdio.h>
#include <stdint.h>

#define mod 660634
#define DIM 2
// Funcție pentru a înmulți două matrici și a returna rezultatul
void multiply_matrices(int A[DIM][DIM], int B[DIM][DIM]) {
    int result[DIM][DIM];
    int i, j, k;
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            result[i][j] = 0;
            for (k = 0; k < DIM; k++) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    // Copiem rezultatul înapoi în matricea A
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            A[i][j] = result[i][j];
        }
    }
}

// Funcție pentru a ridica matricea Z la puterea k
void matrix_power(int result[DIM][DIM], int k,int Z[DIM][DIM]) {
    int temp[DIM][DIM];
    int i, j;

    // Inițializăm matricea rezultat ca fiind matricea identitate
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
            result[i][j] = (i == j) ? 1 : 0;
        }
    }

    // Ridicăm matricea Z la puterea k folosind algoritmul de exponențiere rapidă pentru matrice
    while (k > 0) {
        if (k % 2 == 1) {
            multiply_matrices(result, Z);
        }
        multiply_matrices(Z, Z);
        k /= 2;
    }
}

int main(void)
{
    FILE *f1=fopen("kfib.in","r"),*f2=fopen("kfib.out","w");
    if(f1==NULL||f2==NULL)
    {
        printf("eroare");
        return 1;
    }

    uint32_t k;
    fscanf(f1,"%d",&k);

    int z[2][2]={{0,1},{1,1}};
    int rez[2][2];
    matrix_power(rez,k-1,z);

    fprintf(f2,"%d",rez[1][1]%mod);

    fclose(f1);
    fclose(f2);
    return 0;
}