#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void relax(T &a, const T &b) {
  if (b > a) a = b;
}
long long mod;
inline int modplus(const int &lhs, const int &rhs) {
  int res = lhs + rhs;
  if (res >= mod) res -= mod;
  return res;
}
inline int modmult(const int &lhs, const int &rhs) {
  return (long long)lhs * rhs % mod;
}
inline void _fib(const long long &n, int &resV, int &resPrev) {
  if (n == 1) {
    resV = 1 % mod;
    resPrev = 0;
    return;
  }
  int v, prev;
  if (n & 1) {
    _fib(n - 1, v, prev);
    resV = modplus(v, prev), resPrev = v;
  } else {
    _fib(n >> 1, v, prev);
    resV = modplus(modmult(v, modplus(v, prev)), modmult(prev, v));
    resPrev = modplus(modmult(v, v), modmult(prev, prev));
  }
}
inline long long fib(const long long &n) {
  int v, prev;
  _fib(n, v, prev);
  return v;
}
int main() {
  long long l, r, k;
  cin >> mod >> l >> r >> k;
  l--;
  long long index;
  for (long long i = r, nexti; i > 0ll; i = nexti) {
    long long t1 = l / i, t2 = r / i;
    if (t2 - t1 >= k) {
      index = i;
      break;
    }
    nexti = 0ll;
    relax(nexti, l / (t1 + 1ll));
    relax(nexti, r / (t2 + 1ll));
  }
  cout << fib(index) << endl;
  return 0;
}
