#include <bits/stdc++.h>
long long m;
long long fib(long long n) {
  long long A[2][2] = {{1, 0}, {0, 1}}, B[2][2] = {{1, 1}, {1, 0}}, C[2][2],
            x = 1;
  int i, j, k;
  for (i = 0; i <= 62; i++) {
    if ((x)&n) {
      for (j = 0; j <= 1; j++)
        for (k = 0; k <= 1; k++) C[j][k] = 0;
      for (j = 0; j <= 1; j++)
        for (k = 0; k <= 1; k++)
          for (int p = 0; p <= 1; p++) {
            C[j][k] += A[j][p] * B[p][k];
            C[j][k] %= m;
          }
      for (j = 0; j <= 1; j++)
        for (k = 0; k <= 1; k++) A[j][k] = C[j][k];
    }
    x *= 2;
    for (j = 0; j <= 1; j++)
      for (k = 0; k <= 1; k++) C[j][k] = 0;
    for (j = 0; j <= 1; j++)
      for (k = 0; k <= 1; k++)
        for (int p = 0; p <= 1; p++) {
          C[j][k] += B[j][p] * B[p][k];
          C[j][k] %= m;
        }
    for (j = 0; j <= 1; j++)
      for (k = 0; k <= 1; k++) B[j][k] = C[j][k];
  }
  return A[0][1];
}
int main() {
  long long l, r, i, j, k, K, x, y, z, h;
  scanf("%I64d%I64d%I64d%I64d", &m, &l, &r, &k);
  h = 1;
  for (i = 1; i <= 1000000; i++) {
    j = r / i;
    if (i > h && r / i - (l - 1) / i >= k) h = i;
    if (j > h && r / j - (l - 1) / j >= k) h = j;
  }
  printf("%I64d", fib(h));
  getchar();
  getchar();
}
