#include <bits/stdc++.h>
using namespace std;
typedef long long mx[2][2];
mx a, b, c;
long long d, l, r, k;
void mul(mx x, mx y) {
  memset(c, 0, sizeof(c));
  for (int i = 0; i < (2); ++i)
    for (int j = 0; j < (2); ++j)
      for (int k = 0; k < (2); ++k) (c[i][j] += x[i][k] * y[k][j] % d) %= d;
  memcpy(x, c, sizeof(mx));
}
void pmx(long long x) {
  memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
  a[0][1] = a[1][0] = a[1][1] = 1;
  b[0][0] = b[1][1] = 1;
  while (x) {
    if (x & 1) mul(b, a);
    mul(a, a);
    x >>= 1;
  }
}
int main() {
  cin >> d >> l >> r >> k;
  --l;
  long long x = 1;
  for (long long i = 1; i * i <= r; ++i) {
    long long j = r / i;
    if (r / (i)-l / (i) >= k) x = max(x, i);
    if (r / (j)-l / (j) >= k) x = max(x, j);
  }
  pmx(x);
  cout << b[0][1] % d << endl;
  return 0;
}
