#include <bits/stdc++.h>
using namespace std;
int toInt(string s) {
  istringstream sin(s);
  int t;
  sin >> t;
  return t;
}
template <class T>
string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}
template <class T>
void chmin(T &t, T f) {
  if (t > f) t = f;
}
template <class T>
void chmax(T &t, T f) {
  if (t < f) t = f;
}
int main() {
  long long m, l, r, k;
  cin >> m >> l >> r >> k;
  long long t = 1;
  for (long long x = 1; x * x <= r; x++) {
    long long cnt = r / x - (l - 1) / x;
    if (cnt >= k) chmax(t, x);
    long long y = r / x;
    cnt = r / y - (l - 1) / y;
    if (cnt >= k) chmax(t, y);
  }
  t--;
  long long p[2][2] = {1, 1, 1, 0};
  long long mat[2][2] = {1, 0, 0, 1};
  while (t) {
    long long c[2][2];
    if (t & 1) {
      c[0][0] = (mat[0][0] * p[0][0] % m + mat[0][1] * p[1][0] % m) % m;
      c[1][0] = (mat[1][0] * p[0][0] % m + mat[1][1] * p[1][0] % m) % m;
      c[0][1] = (mat[0][0] * p[0][1] % m + mat[0][1] * p[1][1] % m) % m;
      c[1][1] = (mat[1][0] * p[0][1] % m + mat[1][1] * p[1][1] % m) % m;
      mat[0][0] = c[0][0];
      mat[0][1] = c[0][1];
      mat[1][0] = c[1][0];
      mat[1][1] = c[1][1];
    }
    c[0][0] = (p[0][0] * p[0][0] % m + p[0][1] * p[1][0] % m) % m;
    c[1][0] = (p[1][0] * p[0][0] % m + p[1][1] * p[1][0] % m) % m;
    c[0][1] = (p[0][0] * p[0][1] % m + p[0][1] * p[1][1] % m) % m;
    c[1][1] = (p[1][0] * p[0][1] % m + p[1][1] * p[1][1] % m) % m;
    p[0][0] = c[0][0];
    p[0][1] = c[0][1];
    p[1][0] = c[1][0];
    p[1][1] = c[1][1];
    t >>= 1;
  }
  cout << mat[0][0] % m << endl;
  return 0;
}
