#include <bits/stdc++.h>
using namespace std;
long long a[2000010];
int main() {
  int p;
  long long l, r, m;
  cin >> p >> l >> r >> m;
  int n = 0;
  for (int i = 1; (long long)i * i <= r; i++) {
    a[n++] = i;
    a[n++] = r / i;
  }
  sort(a, a + n);
  long long whi;
  for (int i = n - 1; i >= 0; i--)
    if (r / a[i] - (l - 1) / a[i] >= m) {
      whi = a[i];
      break;
    }
  if (whi <= 2) {
    cout << 1 % p << endl;
    return 0;
  }
  int s[2][2], t[2][2], w[2][2];
  s[0][0] = s[1][1] = 1;
  s[0][1] = s[1][0] = 0;
  t[0][0] = t[0][1] = t[1][0] = 1;
  t[1][1] = 0;
  for (whi -= 2; whi; whi >>= 1) {
    if (whi & 1) {
      memset(w, 0, sizeof(w));
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          for (int k = 0; k < 2; k++)
            w[i][j] = ((long long)s[i][k] * t[k][j] + w[i][j]) % p;
      memcpy(s, w, sizeof(w));
    }
    memset(w, 0, sizeof(w));
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
          w[i][j] = ((long long)t[i][k] * t[k][j] + w[i][j]) % p;
    memcpy(t, w, sizeof(w));
  }
  cout << (s[0][0] + s[1][0]) % p;
  return 0;
}
