#include <bits/stdc++.h>
using namespace std;
long long M;
const int N_MAX = 2;
template <class T>
void mul(int n, const T A[N_MAX][N_MAX], const T x[N_MAX], T y[N_MAX]) {
  static T z[N_MAX];
  for (int i = 0; i < (n); i++) {
    z[i] = 0;
    for (int j = 0; j < (n); j++) z[i] = (z[i] + A[i][j] * x[j]) % M;
  }
  for (int i = 0; i < (n); i++) y[i] = z[i];
}
template <class T>
void mul(int n, const T A[N_MAX][N_MAX], const T B[N_MAX][N_MAX],
         T C[N_MAX][N_MAX]) {
  static T tmp[N_MAX][N_MAX];
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (n); j++) {
      tmp[i][j] = 0;
      for (int k = 0; k < (n); k++)
        tmp[i][j] = (tmp[i][j] + A[i][k] * B[k][j]) % M;
    }
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (n); j++) C[i][j] = tmp[i][j];
}
template <class T>
void pow(int n, const T A[N_MAX][N_MAX], long long m, T B[N_MAX][N_MAX]) {
  static T tmp[N_MAX][N_MAX];
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (n); j++) {
      tmp[i][j] = A[i][j];
      B[i][j] = (i == j ? 1 : 0);
    }
  for (int t = 0; m > 0; t++) {
    if (m & (1LL << t)) {
      mul(n, B, tmp, B);
      m -= 1LL << t;
    }
    mul(n, tmp, tmp, tmp);
  }
}
long long fib(long long n) {
  long long A[2][2] = {{1, 1}, {1, 0}}, x[2] = {1, 0};
  pow(2, A, n - 1, A);
  mul(2, A, x, x);
  return x[0];
}
int main() {
  long long l, r, k;
  cin >> M >> l >> r >> k;
  vector<long long> cand;
  for (long long i = 1; i * i <= r; i++) {
    cand.push_back(i);
    for (int j = -1; j <= 1; j++) {
      cand.push_back(l / i + j);
      cand.push_back(r / i + j);
    }
  }
  long long idx = 1;
  for (int i = 0; i < (cand.size()); i++) {
    long long a = cand[i];
    if (a > 0 && r / a - (l - 1) / a >= k) idx = max(idx, a);
  }
  cout << fib(idx) << endl;
  return 0;
}
