#include <bits/stdc++.h>
long long max(long long a, long long b) { return a > b ? a : b; }
int a[2][2], as[2][2], m;
void cal(int a[2][2], int b[2][2]) {
  int c[2][2], i, j, k;
  long long e;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) {
      e = 0;
      for (k = 0; k < 2; k++) e = (e + (long long)a[i][k] * b[k][j]) % m;
      c[i][j] = e;
    }
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) a[i][j] = c[i][j];
}
int main() {
  long long i, l, r, k, n;
  scanf("%d%I64d%I64d%I64d", &m, &l, &r, &k);
  l--;
  n = 1;
  for (i = 1; i * i <= r; i++) {
    if (r / i - l / i >= k) n = max(n, i);
    if (l / i && r / (l / i) - l / (l / i) >= k) n = max(n, l / i);
    if (r / i && r / (r / i) - l / (r / i) >= k) n = max(n, r / i);
  }
  as[0][0] = 1;
  a[0][0] = a[0][1] = a[1][0] = 1;
  while (n) {
    if (n & 1) cal(as, a);
    n >>= 1;
    cal(a, a);
  }
  printf("%d\n", as[0][1]);
  return 0;
}
