#include <bits/stdc++.h>
using namespace std;
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
const int INF = 1 << 29;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n >> b) & 1; }
inline void set_bit(int& n, int b) { n |= two(b); }
inline void unset_bit(int& n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) {
  int res = 0;
  while (n && ++res) n -= n & (-n);
  return res;
}
template <class T>
void chmax(T& a, const T& b) {
  a = max(a, b);
}
template <class T>
void chmin(T& a, const T& b) {
  a = min(a, b);
}
long long mod, l, r, k;
template <class T>
class Matrix {
 private:
  vector<vector<T> > mat;
  int R, C;

 public:
  Matrix(int RR = 0, int CC = 0, bool unit = false)
      : mat(RR, vector<T>(CC)), R(RR), C(CC) {
    if (unit)
      for (int i = 0; i < (min(R, C)); i++) mat[i][i] = (T)1;
  }
  vector<T>& operator[](int r) { return mat[r]; }
  const vector<T>& operator[](int r) const { return mat[r]; }
  const Matrix<T>& operator=(const Matrix<T>& m) {
    R = m.R;
    C = m.C;
    mat = m.mat;
    return *this;
  }
  Matrix<T> operator*(const Matrix<T>& m) const {
    if (C != m.R) cout << "CHYBA - nekompatibilne matice (*)" << endl;
    Matrix res(R, m.C);
    for (int i = 0; i < (res.R); i++)
      for (int j = 0; j < (res.C); j++)
        for (int k = 0; k < (C); k++)
          res[i][j] = (res[i][j] + mat[i][k] * m[k][j]) % mod;
    return res;
  }
  Matrix<T> operator^(long long n) const {
    if (R != C) cout << "CHYBA - umocnovanie nestvorcovej matice (^)" << endl;
    Matrix res(R, C, true), p(*this);
    while (n) {
      if (n & 1) res = res * p;
      p = p * p;
      n /= 2;
    }
    return res;
  }
};
int main() {
  cin >> mod >> l >> r >> k;
  vector<long long> v;
  for (long long d = 1; d * d <= r; ++d) {
    v.push_back(d);
    v.push_back(r / d);
  }
  for (long long d = 1; d * d <= l; ++d) v.push_back((l + d - 1) / d);
  long long res = 0;
  for (int i = 0; i < (v.size()); i++)
    if (r / v[i] - (l + v[i] - 1) / v[i] + 1 >= k) chmax(res, v[i]);
  Matrix<long long> mat(2, 2);
  mat[0][1] = mat[1][0] = mat[1][1] = 1;
  mat = mat ^ res;
  cout << mat[0][1] << endl;
  return 0;
}
