#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k;
vector<vector<long long> > operator*(const vector<vector<long long> > &a,
                                     const vector<vector<long long> > &b) {
  vector<vector<long long> > ret(2, vector<long long>(2, 0));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      ret[i][j] = 0;
      for (int k = 0; k < 2; k++)
        ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % m;
    }
  }
  return ret;
}
vector<vector<long long> > power(vector<vector<long long> > x, long long p) {
  vector<vector<long long> > ret(2, vector<long long>(2, 0));
  ret[0][0] = ret[1][1] = 1;
  while (p > 0) {
    if (p & 1) ret = ret * x;
    x = x * x;
    p >>= 1;
  }
  return ret;
}
long long fib(long long x) {
  if (x <= 2) return 1 % m;
  vector<vector<long long> > a(2, vector<long long>(2, 0));
  a[0][0] = 1;
  a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 0;
  a = power(a, x - 2);
  return (a[0][0] + a[0][1]) % m;
}
int main() {
  cin >> m >> l >> r >> k;
  long long x = 1;
  for (long long i = 1; i * i <= r; i++) {
    if (r / i - (l - 1) / i >= k) x = max(x, i);
    long long j = r / i;
    if (r / j - (l - 1) / j >= k) x = max(x, j);
  }
  cout << fib(x) << endl;
}
