#include <bits/stdc++.h>
using namespace std;
const int oo = 2147483647;
long long m, n, l, r, k;
struct martix {
  int x, y;
  long long d[3][3];
} e;
long long init() {
  long long i, j, tq = 1;
  for (i = 1; i <= r; i = j + 1) {
    j = r / (r / i);
    if (r / i - (l - 1) / j >= k) tq = max(tq, j);
  }
  return tq;
}
martix operator*(martix a, martix b) {
  martix c;
  int i, j, ij;
  c.x = a.x;
  c.y = b.y;
  memset(c.d, 0, sizeof(c.d));
  for (i = 1; i <= c.x; i++) {
    for (j = 1; j <= c.y; j++) {
      for (ij = 1; ij <= a.y; ij++) {
        c.d[i][j] = (c.d[i][j] + a.d[i][ij] * b.d[ij][j]) % m;
      }
    }
  }
  return c;
}
martix calc(long long v) {
  if (v == 1) return e;
  martix tq;
  tq = calc(v / 2);
  tq = tq * tq;
  if (v % 2) tq = tq * e;
  return tq;
}
int main() {
  cin >> m >> l >> r >> k;
  n = init();
  if (n <= 2) {
    cout << 1 % m << endl;
  } else {
    martix tq, temp;
    e.x = e.y = 2;
    memset(e.d, 0, sizeof(e.d));
    memset(temp.d, 0, sizeof(temp.d));
    e.d[1][1] = 0;
    e.d[1][2] = e.d[2][1] = e.d[2][2] = 1;
    tq = calc(n - 2);
    temp.x = 1;
    temp.y = 2;
    temp.d[1][1] = temp.d[1][2] = 1;
    temp = temp * tq;
    cout << temp.d[1][2] << endl;
  }
}
