#include <bits/stdc++.h>
using namespace std;
long long p, l, r, k;
struct Matrix {
  long long d[2][2];
  Matrix() { d[0][1] = d[1][0] = d[0][0] = d[1][1] = 0; }
};
Matrix operator*(const Matrix& a, const Matrix& b) {
  Matrix ans;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        ans.d[i][j] = (ans.d[i][j] + a.d[i][k] * b.d[k][j]) % p;
  return ans;
}
Matrix pow(Matrix base, long long exp) {
  Matrix ans, mul = base;
  ans.d[0][0] = ans.d[1][1] = 1;
  while (exp) {
    if (exp % 2) ans = ans * mul;
    mul = mul * mul;
    exp /= 2;
  }
  return ans;
}
long long fib(long long i) {
  Matrix m;
  m.d[0][0] = m.d[0][1] = m.d[1][0] = 1;
  return pow(m, i).d[1][0];
}
void proc(long long pos, long long& ans) {
  long long ub = r / pos, lb = l / pos;
  if (l % pos) lb++;
  if (ub - lb + 1 >= k) ans = max(ans, pos);
}
int main() {
  cin >> p >> l >> r >> k;
  long long ans = 0;
  for (long long i = 1; i * i <= r; i++) {
    proc(i, ans);
    proc(r / i, ans);
  }
  for (long long i = 1; i * i <= l; i++)
    if (l % i)
      proc(l / (i - 1), ans);
    else
      proc(l / i, ans);
  cout << fib(ans) << endl;
}
