#include <iostream>

int RFIB(int n, int m) {
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return ((RFIB(n-1, m) + RFIB(n-2, m)) % m);
}

int IFIB(long long n, int m) {
  int a, b;
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else {
    a = 0;
    b = 1;
    for (long long i = 2; i <= n; ++i) {
      int temp = b;
      b = (a+b) % m;
      a = temp;
    }
  }
  return b;
}

int main() {
  clock_t begin = clock();
  // tested on Steven's Acer Predator (2021) gaming desktop
  // printf("%d\n", RFIB(41, 2023)); // 0.688s
  // printf("%d\n", RFIB(46, 2023)); // 7.687s
  printf("%d\n", IFIB(320000000LL, 2023)); // 0.953s
  // printf("%d\n", IFIB(3200000000LL, 2023)); // 9.593s
  printf("computed in = %.12fs\n", (double)(clock()-begin)/CLOCKS_PER_SEC);
  return 0;
}