#include <bits/stdc++.h>
using namespace std;
vector<vector<long long> > multiMatrix(vector<vector<long long> > xMatrix,
                                       vector<vector<long long> > yMatrix,
                                       long long modMatrix) {
  int xRow = xMatrix.size(), xColumn = xMatrix[0].size();
  int yRow = yMatrix.size(), yColumn = yMatrix[0].size();
  if (xColumn != yRow) cout << "NOOOOOOOOOOOOOOOOO" << endl;
  vector<vector<long long> > retMatrix(xRow);
  for (int i = 0; i < retMatrix.size(); i++) retMatrix[i].assign(yColumn, 0);
  for (int i = 0; i < xRow; i++) {
    for (int j = 0; j < yColumn; j++) {
      for (int k = 0; k < xColumn; k++)
        retMatrix[i][j] =
            (retMatrix[i][j] + xMatrix[i][k] * yMatrix[k][j]) % modMatrix;
    }
  }
  return retMatrix;
}
vector<vector<long long> > powerMatrix(vector<vector<long long> > retMatrixPow,
                                       long long nMatrixPow,
                                       long long modMatrixPow) {
  vector<vector<long long> > powMatrixPow = retMatrixPow;
  while (nMatrixPow > 0) {
    if (nMatrixPow & 1)
      retMatrixPow = multiMatrix(retMatrixPow, powMatrixPow, modMatrixPow);
    powMatrixPow = multiMatrix(powMatrixPow, powMatrixPow, modMatrixPow);
    nMatrixPow >>= 1;
  }
  return retMatrixPow;
}
long long Fibonacci(long long countFib, long long modFib) {
  vector<vector<long long> > retFib(2), mulFib(2);
  retFib[0].push_back(0);
  retFib[0].push_back(1);
  retFib[1].push_back(1);
  retFib[1].push_back(1);
  mulFib[0].push_back(0);
  mulFib[1].push_back(1);
  vector<vector<long long> > fibonacci =
      multiMatrix(powerMatrix(retFib, countFib, modFib), mulFib, modFib);
  return fibonacci[0][0];
}
long long mod, l, r, k;
bool check(long long val) { return (r / val - (l - 1) / val) >= k; }
int main() {
  cin >> mod >> l >> r >> k;
  long long ans = 1;
  for (long long i = 1; i * i <= r; i++) {
    if (check(i)) ans = max(ans, i);
    if (check(r / i)) ans = max(ans, r / i);
  }
  cout << Fibonacci(ans - 1, mod) << endl;
  return 0;
}
