#include <bits/stdc++.h>
using namespace std;
const int64_t MAXN = 1e5 + 5;
const int64_t MAXINT = 1e9;
const int64_t MAXLL = 1e18;
int64_t MOD = 1e9 + 7;
struct Matrix {
  int64_t n, m;
  vector<vector<int64_t> > matrix;
  Matrix(int64_t n_, int64_t m_) {
    n = n_;
    m = m_;
    matrix.resize(n);
    for (int64_t i = 0; i < n; ++i) matrix[i].resize(m);
  }
  void ones() {
    if (n != m) return;
    for (int64_t i = 0; i < n; ++i) matrix[i][i] = 1;
  }
};
Matrix operator*(const Matrix &m1, const Matrix &m2) {
  Matrix result(m1.n, m2.m);
  for (int64_t i = 0; i < result.n; ++i) {
    for (int64_t j = 0; j < result.m; ++j) {
      for (int64_t p = 0; p < m1.m; ++p) {
        int64_t prod = (m1.matrix[i][p] * m2.matrix[p][j]) % MOD;
        result.matrix[i][j] = (result.matrix[i][j] + prod) % MOD;
      }
    }
  }
  return result;
}
Matrix binpow(Matrix a, int64_t p) {
  Matrix res(a.n, a.m);
  res.ones();
  while (p) {
    if (p % 2 == 1) {
      res = res * a;
    }
    a = a * a;
    p /= 2;
  }
  return res;
}
int64_t nthfib(int64_t n) {
  Matrix b(2, 2);
  b.matrix[0][0] = 0;
  b.matrix[0][1] = 1;
  b.matrix[1][0] = 1;
  b.matrix[1][1] = 1;
  Matrix fib(1, 2);
  fib.matrix[0][0] = 0;
  fib.matrix[0][1] = 1;
  auto result = fib * binpow(b, n);
  return result.matrix[0][0];
}
int64_t f(int64_t l, int64_t r, int64_t ans) {
  int64_t a = r / ans;
  int64_t b = l / ans + (l % ans > 0);
  return a - b + 1;
}
void solve() {
  int64_t l, r, k;
  cin >> MOD >> l >> r >> k;
  vector<int64_t> good;
  for (int64_t i = 1; i * i <= r; i++) {
    good.push_back(i);
    good.push_back(r / i);
  }
  for (int64_t i = 1; i * i <= l; i++) {
    if (l % i == 0)
      good.push_back(l / i);
    else {
      if (i > 1) good.push_back(l / (i - 1));
    }
  }
  int64_t best = 1;
  for (int64_t ans : good) {
    if (f(l, r, ans) >= k) best = max((int64_t)best, (int64_t)ans);
  }
  cout << nthfib(best) << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}
