#include <bits/stdc++.h>
using namespace std;
struct M {
  long long a[2][2];
  M() { memset(a, 0, sizeof a); }
  M pom(const M &s, long long mod) const {
    M r;
    for (int k = (0); k < (2); k++)
      for (int i = (0); i < (2); i++)
        for (int j = (0); j < (2); j++) {
          r.a[i][j] = (r.a[i][j] + a[i][k] * s.a[k][j]) % mod;
        }
    return r;
  }
};
M qp(M m, long long st, long long mod) {
  M r;
  r.a[0][0] = r.a[1][1] = 1 % mod;
  while (st) {
    if (st & 1) r = r.pom(m, mod);
    m = m.pom(m, mod);
    st >>= 1;
  }
  return r;
}
long long fb(long long pos, long long mod) {
  if (pos <= 2) return 1 % mod;
  M m;
  m.a[0][0] = 1 % mod;
  m.a[1][0] = 1 % mod;
  m.a[0][1] = 1 % mod;
  M t = qp(m, pos - 1, mod);
  return t.a[0][0];
}
bool good(long long l, long long r, long long d, long long k) {
  if (d <= 1) return 0;
  return (r / d) - (l - 1) / d >= k;
}
long long solve(long long l, long long r, long long k) {
  long long best = 1;
  for (int i = (1); i < (1111111); i++)
    if (good(l, r, i, k)) best = i;
  for (long long rd = 1; rd <= 1000000; rd++)
    for (int dx = (-1); dx < (2); dx++)
      for (int dx2 = (-1); dx2 < (2); dx2++) {
        long long d = (r + dx) / rd + dx2;
        if (good(l, r, d, k)) best = max(best, d);
        d = (l + dx) / rd + dx2;
        if (good(l, r, d, k)) best = max(best, d);
      }
  return best;
}
int main() {
  long long m, l, r, k;
  cin >> m >> l >> r >> k;
  cout << fb(solve(l, r, k), m) << endl;
  return 0;
}
