#include <bits/stdc++.h>
using namespace std;
long long MOD, l, r, k, ans;
bool judge(long long x) {
  long long tmp = (r / x) + (1 - l) / x;
  if (tmp >= k) return true;
  return false;
}
struct mt {
  long long a[2][2];
};
mt multi(mt a, mt b, long long mod) {
  mt res;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      res.a[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        res.a[i][j] += a.a[i][k] * b.a[k][j] % mod;
        res.a[i][j] % mod;
      }
    }
  return res;
}
mt power(mt a, long long b, long long mod) {
  mt res;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) res.a[i][j] = 0;
  res.a[0][0] = res.a[1][1] = 1;
  while (b) {
    if (b & 1) res = multi(res, a, mod);
    b >>= 1;
    a = multi(a, a, mod);
  }
  return res;
}
long long F(long long n) {
  mt tmp, q;
  tmp.a[0][0] = 1;
  tmp.a[0][1] = 0;
  tmp.a[1][0] = 0;
  tmp.a[1][1] = 0;
  q.a[0][0] = 1;
  q.a[0][1] = 1;
  q.a[1][0] = 1;
  q.a[1][1] = 0;
  q = power(q, n - 1, MOD);
  tmp = multi(tmp, q, MOD);
  return tmp.a[0][0];
}
int main() {
  scanf("%lld%lld%lld%lld", &MOD, &l, &r, &k);
  for (long long i = 1; i <= sqrt(r); i++) {
    if (judge(i)) ans = max(ans, i);
    if (judge(r / i)) ans = max(ans, r / i);
  }
  printf("%lld", F(ans));
  return 0;
}
