#include <bits/stdc++.h>
using namespace std;
int a[1000009], sum[1000009], m;
struct pi {
  long long ah[2][2];
  pi() {
    ah[0][0] = ah[1][1] = 1;
    ah[0][1] = ah[1][0] = 0;
  }
};
pi multi(pi x, pi y) {
  pi z;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      z.ah[i][j] = 0;
      for (int k = 0; k < 2; k++)
        z.ah[i][j] = (z.ah[i][j] % m + x.ah[i][k] % m * y.ah[k][j] % m) % m;
      z.ah[i][j] %= m;
    }
  }
  return z;
}
pi quimul(pi x, long long int n) {
  pi an;
  for (; n; n >>= 1) {
    if (n & 1) an = multi(an, x);
    x = multi(x, x);
  }
  return an;
}
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
int main() {
  long long int n, l, r;
  cin >> m >> l >> r >> n;
  long long int ans = -1;
  for (long long int i = 1; i * i <= r; i++) {
    if (r / i - (l - 1) / i >= n) ans = max(ans, i);
    if (r / (r / i) - (l - 1) / (r / i) >= n) ans = max(ans, r / i);
  }
  if (m == 1)
    cout << 0 << endl;
  else if (ans <= 2)
    cout << 1 << endl;
  else {
    pi aha;
    aha.ah[0][0] = 1;
    aha.ah[0][1] = 1;
    aha.ah[1][0] = 1;
    aha.ah[1][1] = 0;
    aha = quimul(aha, ans - 1);
    cout << (aha.ah[0][0] + m) % m << endl;
  }
}
