#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k;
long long re[3][3], ma[3][3];
long long n;
void mul(long long a[3][3], long long b[3][3]) {
  long long c[3][3];
  memset(c, 0, sizeof(c));
  for (int i = 1; i <= 2; ++i) {
    for (int j = 1; j <= 2; ++j) {
      for (int k = 1; k <= 2; ++k) {
        c[i][j] += a[i][k] * b[k][j] % m;
        c[i][j] %= m;
      }
    }
  }
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= 2; ++j) a[i][j] = c[i][j] % m;
}
long long getfib(long long n) {
  ma[1][1] = 0, ma[1][2] = 1 % m, ma[2][1] = 1 % m, ma[2][2] = 1 % m;
  re[1][1] = 1, re[1][2] = 0, re[2][1] = 0, re[2][2] = 1;
  while (n) {
    if (n & 1) mul(re, ma);
    mul(ma, ma);
    n >>= 1;
  }
  return re[2][1] % m;
}
int main() {
  scanf("%lld%lld%lld%lld", &m, &l, &r, &k);
  --l;
  for (long long i = 1; i * i <= r; ++i) {
    if (r / i - l / i >= k) n = max(n, i);
    if (l / i)
      if (r / (l / i) - l / (l / i) >= k) n = max(n, l / i);
    if (r / (r / i) - l / (r / i) >= k) n = max(n, r / i);
  }
  printf("%lld\n", getfib(n));
  return 0;
}
