#include <bits/stdc++.h>
using namespace std;
long long l, r, k;
long long m;
long long m0[2][2] = {1, 0, 0, 1};
long long m1[2][2] = {1, 1, 1, 0};
long long c[2][2];
void mul(long long res[2][2], long long a[2][2]) {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      c[i][j] = 0;
      for (int k = 0; k < 2; k++) c[i][j] += (res[i][k] * a[k][j]) % m;
      c[i][j] %= m;
    }
  memcpy(res, c, sizeof(c));
}
long long solve() {
  long long s = 1;
  for (long long i = 1; i * i <= r; i++) {
    if (r / i - (l - 1) / i >= k && i > s) {
      s = i;
    }
    long long e = r / i;
    if (i - (l - 1) / e >= k && e > s) s = e;
  }
  return s;
}
int main() {
  scanf("%I64d %I64d %I64d %I64d", &m, &l, &r, &k);
  long long n = solve();
  if (n <= 2)
    printf("%lld\n", 1 % m);
  else {
    n -= 2;
    while (n) {
      if (n & 1) mul(m0, m1);
      mul(m1, m1);
      n /= 2;
    }
    printf("%lld\n", (m0[0][0] + m0[0][1]) % m);
  }
  return 0;
}
