#include <bits/stdc++.h>
void multi(long long a[][2], long long b[][2], long long r[][2], int m) {
  int i, j, k;
  for (i = 0; i < 2; ++i)
    for (j = 0; j < 2; ++j) {
      r[i][j] = 0;
      for (k = 0; k < 2; ++k) r[i][j] = (r[i][j] + a[i][k] * b[k][j]) % m;
    }
}
int getfib(long long n, int m) {
  long long fib[2] = {0, 1};
  long long mat[2][2] = {{0, 1}, {1, 1}};
  long long res[2][2] = {{1, 0}, {0, 1}};
  long long tmp[2][2];
  while (n) {
    if (n & 1) {
      multi(res, mat, tmp, m);
      memcpy(res, tmp, sizeof(res));
    }
    multi(mat, mat, tmp, m);
    memcpy(mat, tmp, sizeof(mat));
    n >>= 1;
  }
  return res[1][0] % m;
}
int main() {
  int m;
  long long l, r, k;
  while (~scanf("%d%I64d%I64d%I64d", &m, &l, &r, &k)) {
    long long res = 1;
    long long mi;
    double s;
    double e = 1.0 / 900;
    for (s = e; s < 1 - e; s += e) {
      long long l1 = 1, r1 = r;
      while (l1 < r1) {
        mi = l1 * s + r1 * (1 - s);
        if (r / mi - (l - 1) / mi >= k)
          l1 = mi + 1;
        else
          r1 = mi;
      }
      --l1;
      if (l1 > res) res = l1;
    }
    printf("%d\n", getfib(res, m));
  }
  return 0;
}
