#include <bits/stdc++.h>
using namespace std;
long long MOD;
long long getFibb(long long n) {
  long long a11 = 1, a12 = 1, a21 = 1, a22 = 0;
  long long r11 = 1, r12 = 0;
  long long q11 = 0, q12 = 0, q21 = 0, q22 = 0;
  while (n > 0) {
    if (n & 1) {
      q11 = (r11 * a11 + r12 * a21) % MOD;
      q12 = (r11 * a12 + r12 * a22) % MOD;
      r11 = q11;
      r12 = q12;
    }
    q11 = (a11 * a11 + a12 * a21) % MOD;
    q12 = (a11 * a12 + a12 * a22) % MOD;
    q21 = (a21 * a11 + a22 * a21) % MOD;
    q22 = (a21 * a12 + a22 * a22) % MOD;
    a11 = q11;
    a12 = q12;
    a21 = q21;
    a22 = q22;
    n >>= 1;
  }
  return r12;
}
long long m, l, r, k, ans;
long long cnt(long long L, long long R, long long X) {
  return ((R / X) - ((L - 1) / X));
}
int main() {
  cin >> m >> l >> r >> k;
  MOD = m;
  for (long long i = 1; i * i <= r; i++) {
    if (cnt(l, r, i) >= k) ans = max(ans, i);
    if (cnt(l, r, r / i) >= k) ans = max(ans, r / i);
  }
  cout << getFibb(ans);
  return 0;
}
