#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k, ans;
map<long long, long long> memo;
long long F(long long x) {
  if (x == 0) return 0;
  if (x == 1) return 1 % m;
  auto d = memo.find(x);
  if (d != memo.end()) return d->second;
  if (x & 1) {
    long long n = x / 2 + 1;
    long long a = F(n - 1);
    long long b = F(n);
    return memo[x] = (a * a % m + b * b % m) % m;
  } else {
    long long n = x / 2;
    long long a = F(n - 1);
    long long b = F(n);
    return memo[x] = (2 * a % m * b % m + b * b % m) % m;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> m >> l >> r >> k;
  l--;
  set<long long> index;
  for (long long i = 1, la; l > 0 and i <= l; i = la + 1) {
    la = l / (l / i);
    index.insert(la);
  }
  for (long long i = 1, la; i <= r; i = la + 1) {
    la = r / (r / i);
    index.insert(la);
  }
  ans = 1;
  for (long long x : index)
    if (r / x - l / x >= k) ans = x;
  ans = F(ans);
  cout << ans << endl;
  return 0;
}
