#include <bits/stdc++.h>
using namespace std;
int MOD;
vector<long long> dif_pos;
struct matr {
  long long m[2][2];
};
matr operator*(matr a, matr b) {
  matr res;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      res.m[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
      }
    }
  return res;
}
matr power(matr m, long long p) {
  if (p == 1) return m;
  if (p % 2) return m * power(m, p - 1);
  return power(m * m, p / 2);
}
int fib(long long num) {
  if (num == 1) return 1;
  matr f;
  f.m[0][0] = 0;
  f.m[0][1] = f.m[1][0] = f.m[1][1] = 1;
  f = power(f, num);
  return f.m[0][1];
}
int main() {
  long long l, r, k;
  cin >> MOD >> l >> r >> k;
  if (MOD == 1) {
    cout << "0\n";
    return 0;
  }
  for (long long d = 1; d * d <= r; d++) {
    dif_pos.push_back(d);
    dif_pos.push_back(r / d);
  }
  for (long long d = 1; d * d <= l; d++) {
    dif_pos.push_back(l / d);
  }
  long long ans = 0;
  for (int i = 0; i < int(dif_pos.size()); i++) {
    long long hi = r / dif_pos[i];
    long long lo = (l - 1) / dif_pos[i];
    if (hi - lo >= k) ans = max(ans, dif_pos[i]);
  }
  cout << fib(ans) << endl;
  return 0;
}
