#include <bits/stdc++.h>
using namespace std;
long long m;
struct mat {
  long long a[2][2];
  mat() {}
  mat(const mat& z) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        a[i][j] = z.a[i][j];
      }
    }
  }
  mat mult(mat z) {
    mat res;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        res.a[i][j] = 0;
        for (int k = 0; k < 2; k++) {
          res.a[i][j] += (a[i][k] * z.a[k][j]) % m;
          res.a[i][j] %= m;
        }
      }
    }
    return res;
  }
};
mat pw(mat x, long long p) {
  if (p == 1) return x;
  mat z = pw(x, p / 2);
  z = z.mult(z);
  if (p % 2 == 0) return z;
  return z.mult(x);
}
long long res = 1;
long long l, r, k;
void check(long long x) {
  if (!x) return;
  if (r / x - (l - 1) / x >= k) res = max(res, x);
}
int main() {
  cin >> m >> l >> r >> k;
  mat in;
  in.a[0][0] = 0;
  in.a[0][1] = 1;
  in.a[1][1] = 1;
  in.a[1][0] = 1;
  for (long long i = 1; i * i <= r; i++) {
    check(i);
    check(r / i);
    check(l / i);
  }
  if (res != 1) {
    mat rr = pw(in, res - 1);
    res = rr.a[1][1];
  }
  res %= m;
  cout << res << endl;
  return 0;
}
