#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
template <class T>
typename T::value_type arr_sum(const T& v, int n) {
  typename T::value_type sum = 0;
  for (int i = (0); i < (n); ++i) sum += v[i];
  return sum;
}
struct Sync_stdio {
  Sync_stdio() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
  }
} _sync_stdio;
int mod;
struct Matrix {
  vector<vector<long long>> mat;
  Matrix(int n, int m) : mat(n, vector<long long>(m)) {}
  vector<long long>& operator[](int t) { return mat[t]; }
  const vector<long long>& operator[](int t) const { return mat[t]; }
  Matrix operator*(const Matrix& m1) const {
    assert(mat[0].size() == m1.mat.size());
    int n = mat.size();
    int m = mat[0].size();
    int k = m1.mat[0].size();
    Matrix m2(mat.size(), m1.mat[0].size());
    for (int i = (0); i < (n); ++i) {
      for (int j = (0); j < (m); ++j) {
        for (int l = (0); l < (k); ++l) {
          m2[i][l] += mat[i][j] * m1[j][l];
          m2[i][l] %= mod;
        }
      }
    }
    return m2;
  }
};
Matrix pow(Matrix m, long long t) {
  assert(m.mat.size() == m[0].size());
  if (t == 0) {
    Matrix res = Matrix(m.mat.size(), m.mat.size());
    for (int i = (0); i < (m.mat.size()); ++i) {
      res[i][i] = 1;
    }
    return res;
  }
  if (t % 2 == 1) {
    return pow(m, t - 1) * m;
  }
  Matrix b = pow(m, t / 2);
  return b * b;
}
long long fib(long long x) {
  Matrix m(2, 2);
  m[0][0] = 1;
  m[0][1] = 1;
  m[1][0] = 1;
  m[1][1] = 0;
  return (pow(m, x))[1][0];
}
long long l, r, k;
long long f(long long x) {
  if (x <= 0) {
    return 0;
  }
  if (x > r) {
    return 0;
  }
  long long l1 = (l + x - 1) / x;
  long long l2 = r / x;
  return l2 - l1 + 1;
}
int main() {
  cin >> mod >> l >> r >> k;
  long long best = 1;
  long long C = 2e6;
  for (int i = (1); i < (min(r + 1, C)); ++i) {
    if (f(i) >= k) {
      best = i;
    }
  }
  for (int i = (1); i < (C); ++i) {
    long long j = r / i;
    for (int l = (-5); l < (5); ++l) {
      if (f(j + l) >= k) {
        best = max(best, j + l);
      }
    }
  }
  for (int i = (1); i < (C); ++i) {
    long long j = l / i;
    for (int l = (-5); l < (5); ++l) {
      if (f(j + l) >= k) {
        best = max(best, j + l);
      }
    }
  }
  cout << fib(best);
}
