#include <bits/stdc++.h>
using namespace std;
long long mat[2][2];
void fibo(long long n, long long m) {
  if (n == 1) {
    mat[0][0] = 1 % m;
    mat[0][1] = 1 % m;
    mat[1][0] = 1 % m;
    mat[1][1] = 0;
    return;
  }
  if (n & 1) {
    fibo(n - 1, m);
    long long x, y, z, w;
    x = mat[0][0];
    y = mat[0][1];
    z = mat[1][0];
    w = mat[1][1];
    mat[0][0] = (x + z) % m;
    mat[0][1] = (y + w) % m;
    mat[1][0] = x;
    mat[1][1] = y;
    return;
  }
  fibo(n >> 1, m);
  long long x, y, z, w;
  x = mat[0][0];
  y = mat[0][1];
  z = mat[1][0];
  w = mat[1][1];
  mat[0][0] = ((x * x) % m + (y * z) % m) % m;
  mat[0][1] = ((x * y) % m + (y * w) % m) % m;
  mat[1][0] = ((z * x) % m + (w * z) % m) % m;
  mat[1][1] = ((z * y) % m + (w * w) % m) % m;
  return;
}
long long total(long long l, long long r, long long n) {
  long long e1 = r / n;
  long long e2 = l / n + 1;
  if (l % n == 0) e2--;
  return e1 - e2 + 1;
}
int main() {
  long long m, l, r, k;
  cin >> m >> l >> r >> k;
  long long ans = 1, max1, max2;
  if (k == 1)
    ans = r;
  else {
    for (long long i = 1; i * i < r; i++) {
      if (total(l, r, i) >= k) ans = max(ans, i);
      long long val = r / i;
      if (total(l, r, val) >= k) ans = max(ans, val);
    }
  }
  fibo(ans, m);
  cout << mat[0][1] << endl;
  return 0;
}
