#include <bits/stdc++.h>
using namespace std;
long long l, r, k, m;
struct matrix {
  vector<vector<long long> > M;
  vector<long long>& operator[](int x) { return M[x]; }
  int size() { return (int)M.size(); }
  matrix(int n, int m) { M.assign(n + 1, vector<long long>(m + 1, 0LL)); }
};
long long add(long long a, long long b) {
  a += b;
  if (a > m) a -= m;
  return a;
}
matrix operator*(matrix a, matrix b) {
  int n = a.size() - 1, q = a[0].size() - 1, p = b[0].size() - 1;
  matrix res = matrix(n, p);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= q; ++j)
      for (int k = 1; k <= p; ++k)
        res[i][k] = add(res[i][k], a[i][j] * b[j][k] % m);
  return res;
}
matrix pw(matrix a, long long n) {
  if (n == 1) return a;
  matrix tmp = pw(a, n >> 1);
  if (n & 1) return tmp * tmp * a;
  return tmp * tmp;
}
int main() {
  cin >> m >> l >> r >> k;
  vector<long long> t;
  long long res = 0;
  for (int i = 1; 1LL * i * i <= r; ++i) {
    t.push_back(i);
    if (i != r / i) t.push_back(r / i);
  }
  for (int i = 0; i < t.size(); ++i)
    if (r / t[i] - (l - 1) / t[i] >= k) res = max(res, t[i]);
  matrix ans = matrix(1, 2);
  matrix c = matrix(2, 2);
  ans[1][1] = 0, ans[1][2] = 1;
  c[1][1] = c[1][2] = c[2][1] = 1;
  ans = ans * pw(c, res + 1);
  cout << ans[1][2];
}
