#include <bits/stdc++.h>
using namespace std;
double EPS = 1e-10;
double EQ(double a, double b) { return abs(a - b) < EPS; }
void fast_stream() { std::ios_base::sync_with_stdio(0); }
template <class T>
string IntToString(T num) {
  string res;
  stringstream ss;
  ss << num;
  return ss.str();
}
long long StringToInt(string &str) {
  long long res = 0;
  for (int i = 0; i < (int)str.size(); i++) res = (res * 10 + str[i] - '0');
  return res;
}
long long mod;
vector<vector<long long> > mulm(vector<vector<long long> > &A,
                                vector<vector<long long> > &B) {
  vector<vector<long long> > C(A.size(), vector<long long>(B[0].size()));
  for (int i = 0; i < (int)A.size(); i++)
    for (int k = 0; k < (int)B.size(); k++)
      for (int j = 0; j < (int)B[0].size(); j++)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
  return C;
}
vector<vector<long long> > pow(vector<vector<long long> > A, long long n) {
  vector<vector<long long> > B(A.size(), vector<long long>(A.size()));
  for (int i = 0; i < (int)A.size(); i++) B[i][i] = 1;
  while (n > 0) {
    if (n & 1) B = mulm(B, A);
    A = mulm(A, A);
    n >>= 1;
  }
  return B;
}
long long calcFib(long long n) {
  vector<vector<long long> > A(2, vector<long long>(2, 0));
  A[0][0] = A[0][1] = A[1][0] = 1;
  A = pow(A, n);
  return (A[1][0] + A[1][1]) % mod;
}
long long l, r, k;
void solve(long long n, vector<long long> &cand) {
  if (n == 0) return;
  long long i = 1;
  for (i = 1; i * i <= n; i++) cand.push_back(i);
  for (long long j = i; j >= 1; j--) {
    if (n / j != 0) cand.push_back(n / j);
  }
}
int main() {
  cin >> mod >> l >> r >> k;
  long long ans = 1;
  vector<long long> cand;
  solve(l - 1, cand);
  solve(r, cand);
  for (int i = 0; i < (int)cand.size(); i++) {
    long long q = cand[i];
    if (q == 0) continue;
    long long cnt = r / q - (l - 1) / q;
    if (cnt >= k) ans = max(ans, q);
  }
  cout << calcFib(ans - 1) % mod << endl;
  return 0;
}
