#include <bits/stdc++.h>
using namespace std;
long long mod;
long long const inf = 2e18;
inline long long add(long long a, long long b) {
  return (a % mod + b % mod + mod) % mod;
}
inline long long mul(long long a, long long b) {
  return (a % mod * b % mod + mod) % mod;
}
inline long long sub(long long a, long long b) {
  return (a % mod - b % mod + mod) % mod;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long modexp(long long x, long long n) {
  if (n == 0) {
    return 1;
  } else if (n & 1) {
    return (modexp((x * x) % mod, n / 2) % mod * x % mod) % mod;
  } else {
    return (modexp((x * x) % mod, n / 2) % mod);
  }
}
long long modinv(long long n) { return modexp(n, mod - 2); }
void multiply(long long F[2][2], long long M[2][2]);
void power(long long F[2][2], long long n);
long long fib(long long n) {
  long long F[2][2] = {{1, 1}, {1, 0}};
  if (n == 0) return 0;
  power(F, n - 1);
  return (F[0][0]) % mod;
}
void power(long long F[2][2], long long n) {
  if (n == 0 || n == 1) return;
  long long M[2][2] = {{1, 1}, {1, 0}};
  power(F, n / 2LL);
  multiply(F, F);
  if (n % 2LL != 0) multiply(F, M);
}
void multiply(long long F[2][2], long long M[2][2]) {
  long long x = add(mul(F[0][0], M[0][0]), mul(F[0][1], M[1][0]));
  long long y = add(mul(F[0][0], M[0][1]), mul(F[0][1], M[1][1]));
  long long z = add(mul(F[1][0], M[0][0]), mul(F[1][1], M[1][0]));
  long long w = add(mul(F[1][0], M[0][1]), mul(F[1][1], M[1][1]));
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
void solve() {
  long long m, l, r, k;
  cin >> m >> l >> r >> k;
  mod = m;
  long long x = 1;
  for (long long i = 1; (i * i) <= r; i++) {
    long long cur = (r / i);
    if ((r / cur) - ((l - 1) / cur) >= k) {
      x = max(cur, x);
    }
    if ((r / i) - ((l - 1) / i) >= k) x = max(x, i);
  }
  cout << fib(x) % mod << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long T = 1;
  for (int t = 1; t <= T; t++) {
    solve();
  }
  return 0;
}
