#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &item) {
  out << '(' << item.first << ", " << item.second << ')';
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const auto &item : v) out << item << ' ';
  return out;
}
int x[2][2], y[2][2];
void mul(int a[2][2], int b[2][2], int c[2][2], int mod) {
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      c[i][j] = (1LL * a[i][0] * b[0][j] + 1LL * a[i][1] * b[1][j]) % mod;
}
void pw(ll exp, int mod) {
  int aux[2][2];
  y[0][0] = y[1][1] = 1 % mod;
  y[0][1] = y[1][0] = 0;
  for (; exp; exp >>= 1) {
    if (exp & 1) {
      mul(x, y, aux, mod);
      memcpy(y, aux, sizeof aux);
    }
    mul(x, x, aux, mod);
    memcpy(x, aux, sizeof aux);
  }
}
int fib(ll n, int mod) {
  if (n <= 2) return 1 % mod;
  x[0][0] = 0;
  x[0][1] = x[1][0] = x[1][1] = 1 % mod;
  pw(n - 1, mod);
  return (y[0][0] + y[1][0]) % mod;
}
ll l, r, k;
ll collect(ll n) {
  if (n == 0) return 0;
  ll kk, res = 0;
  for (ll x = 1; x * x <= n; ++x) {
    if (r / x - (l - 1) / x >= k) res = max(res, x);
    kk = n / x;
  }
  for (; kk; --kk) {
    ll x = n / kk;
    if (r / x - (l - 1) / x >= k) res = max(res, x);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  ll mod;
  cin >> mod >> l >> r >> k;
  ll ans = collect(l - 1);
  ans = max(ans, collect(r));
  cout << fib(ans, mod) << '\n';
  return 0;
}
