#include <bits/stdc++.h>
using namespace std;
bool check(int64_t l, int64_t r, int64_t k, int64_t x) {
  l = l % x != 0 ? x * (l / x + 1) : l;
  return (r - l) / x + 1 >= k;
}
int64_t FIB_MATRIX[2][2] = {{1, 1}, {1, 0}};
void mymul(int64_t a[2][2], int64_t b[2][2], int64_t m, int64_t ret[2][2]) {
  int64_t tmp[2][2] = {0};
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++) {
        tmp[i][j] += a[i][k] * b[k][j];
        tmp[i][j] %= m;
      }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) ret[i][j] = tmp[i][j] % m;
}
void mypow(int64_t a[2][2], int64_t x, int64_t m, int64_t ret[2][2]) {
  int64_t tmp[2][2] = {0};
  if (x == 1) {
    memcpy(tmp, a, sizeof(tmp));
    memcpy(ret, tmp, sizeof(tmp));
    return;
  }
  mypow(a, x / 2, m, tmp);
  mymul(tmp, tmp, m, tmp);
  if (x % 2 == 1) mymul(tmp, a, m, tmp);
  memcpy(ret, tmp, sizeof(tmp));
}
int64_t fib(int64_t n, int64_t m) {
  if (n < 3) return 1 % m;
  int64_t ret[2][2] = {0};
  mypow(FIB_MATRIX, n - 1, m, ret);
  return ret[0][0] % m;
}
int main() {
  int64_t m, l, r, k;
  cin >> m >> l >> r >> k;
  int64_t ans = 0;
  for (int64_t x = 1; x * x <= r; x++) {
    if (check(l, r, k, ((x) < 3 ? 1 : (x))) && x > ans) ans = x;
    if (check(l, r, k, ((r / x) < 3 ? 1 : (r / x))) && r / x > ans) ans = r / x;
  }
  cout << fib(ans, m) << endl;
  return 0;
}
