#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > mult(const vector<vector<int> > &a,
                          const vector<vector<int> > &b, int mod) {
  int n = a.size();
  vector<vector<int> > c(n, vector<int>(n, 0));
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j] % mod) % mod;
  return c;
}
int fib(long long n, int mod) {
  vector<vector<int> > v(2, vector<int>(2, 1));
  v[1][1] = 0;
  vector<vector<int> > r(2, vector<int>(2, 0));
  r[0][0] = r[1][1] = 1 % mod;
  while (n > 0) {
    if (n & 1) r = mult(r, v, mod);
    v = mult(v, v, mod);
    n >>= 1;
  }
  return r[0][1] % mod;
}
int main() {
  int m;
  long long l, r, k;
  cin >> m >> l >> r >> k;
  --l;
  long long g = 1;
  for (long long gcd = 1; gcd * gcd <= r; ++gcd) {
    if (r / gcd - l / gcd >= k) g = max(g, gcd);
    long long q = r / gcd;
    if (r / q - l / q >= k) g = max(g, q);
  }
  cout << fib(g, m) << endl;
}
