#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k;
struct Matrix {
  long long W[2][2];
};
Matrix operator*(const Matrix& A, const Matrix& B) {
  Matrix S;
  memset(S.W, 0, sizeof(S.W));
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int l = 0; l < 2; ++l)
        S.W[i][j] = (S.W[i][j] + A.W[i][l] * B.W[l][j]) % m;
  return S;
}
Matrix operator^(Matrix A, long long e) {
  Matrix S;
  S.W[0][0] = S.W[1][1] = 1;
  S.W[0][1] = S.W[1][0] = 0;
  while (e) {
    if (e & 1) S = S * A;
    A = A * A;
    e >>= 1;
  }
  return S;
}
long long gcd() {
  long long s = 1;
  for (long long i = 1; i * i <= r; ++i) {
    if (r / i - (l - 1) / i >= k && i > s) s = i;
    long long e = r / i;
    if (i - (l - 1) / e >= k && e > s) s = e;
  }
  return s;
}
int main() {
  cin >> m >> l >> r >> k;
  long long n = gcd();
  if (n <= 2)
    cout << 1 % m << endl;
  else {
    Matrix D, S;
    D.W[0][0] = 0;
    D.W[0][1] = D.W[1][0] = D.W[1][1] = 1;
    S = D ^ (n - 2);
    cout << (S.W[0][1] + S.W[1][1]) % m << endl;
  }
  return 0;
}
