#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k, ans;
map<long long, long long> F;
long long f(long long n) {
  if (F.count(n)) return F[n];
  long long k = n / 2;
  if (n % 2 == 0) return F[n] = (f(k) * f(k) + f(k - 1) * f(k - 1)) % m;
  return F[n] = (f(k) * f(k + 1) + f(k - 1) * f(k)) % m;
}
vector<long long> poss;
void get(long long x) {
  for (long long i = 1, la; i <= x; i = la + 1) {
    la = x / (x / i);
    poss.push_back(la);
  }
}
int32_t main() {
  cin >> m >> l >> r >> k;
  get(l - 1), get(r);
  for (auto i : poss)
    if (r / i - (l - 1) / i >= k) ans = max(ans, i);
  F[0] = F[1] = 1 % m;
  cout << f(ans - 1);
  return 0;
}
