#include <bits/stdc++.h>
using namespace std;
const long long maxq = (long long)1e6 + 100;
long long mode;
inline long long add(long long a, long long b) {
  if ((a += b) >= mode) a -= mode;
  return a;
}
inline long long mult(long long a, long long b) { return (a * b) % mode; }
long long F(long long n) {
  int m[2][2];
  m[0][0] = 1;
  m[0][1] = 1;
  m[1][0] = 1;
  m[1][1] = 0;
  long long res[2][2];
  long long t[2][2];
  res[0][0] = 1;
  res[1][0] = 0;
  res[0][1] = 0;
  res[1][1] = 1;
  while (n) {
    if (n & 1) {
      memset(t, 0, sizeof t);
      for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
          for (int k = 0; k < 2; k++) {
            t[i][j] = add(t[i][j], mult(res[i][k], m[k][j]));
          }
        }
      }
      for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
          res[i][j] = t[i][j];
        }
      }
    }
    n >>= 1LL;
    memset(t, 0, sizeof t);
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          t[i][j] = add(t[i][j], mult(m[i][k], m[k][j]));
        }
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        m[i][j] = t[i][j];
      }
    }
  }
  return res[0][0];
}
int main() {
  cin >> mode;
  long long L, R;
  cin >> L >> R;
  long long K;
  cin >> K;
  long long res = 0;
  for (long long m = 1; m < maxq && m <= R; m++) {
    if (R / m - (L - 1) / m >= K) {
      res = max(m, res);
    }
  }
  { fprintf(stderr, "!!!!\n"), fflush(stderr); };
  long long m = R + 1;
  while (m >= maxq) {
    long long valL = (L - 1) / m;
    long long valR = R / m;
    if (valR - valL >= K) {
      res = max(m, res);
      break;
    }
    long long left_asdsadsadsadsa = 0;
    long long right_asdasdsadasda = m;
    while (left_asdsadsadsadsa + 1 < right_asdasdsadasda) {
      long long ave = (left_asdsadsadsadsa + right_asdasdsadasda) / 2;
      if ((L - 1) / ave != valL) {
        left_asdsadsadsadsa = ave;
      } else {
        right_asdasdsadasda = ave;
      }
    }
    long long valM = left_asdsadsadsadsa;
    left_asdsadsadsadsa = 0;
    right_asdasdsadasda = m;
    while (left_asdsadsadsadsa + 1 < right_asdasdsadasda) {
      long long ave = (left_asdsadsadsadsa + right_asdasdsadasda) / 2;
      if (R / ave != valR) {
        left_asdsadsadsadsa = ave;
      } else {
        right_asdasdsadasda = ave;
      }
    }
    m = max(valM, left_asdsadsadsadsa);
  }
  cout << F(res - 1) % mode << endl;
  return 0;
}
