#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k, ans;
map<long long, long long> ff;
long long f(long long n) {
  if (n <= 2) return 1;
  if (ff.find(n) != ff.end()) return ff[n];
  if (n & 1) {
    long long a = f(n / 2 + 1), b = f(n / 2);
    return ff[n] = (a * a % m + b * b % m) % m;
  }
  long long b = f(n / 2 + 1), c = f(n / 2 - 1);
  return ff[n] = ((b * b % m - c * c % m) % m + m) % m;
}
bool ok(long long x) { return r / x - (l - 1) / x >= k; }
int main() {
  cin >> m >> l >> r >> k;
  for (long long i = 1; i * i <= r; i++) {
    if (ok(i)) ans = max(ans, i);
    if (ok(r / i)) ans = max(ans, r / i);
  }
  cout << f(ans) % m;
}
