#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
long long M, L, R, K;
void multi(long long a[2][2], long long b[2][2], long long c[2][2]) {
  int i, j, k;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) {
      c[i][j] = 0;
      for (k = 0; k < 2; k++) c[i][j] += a[i][k] * b[k][j] % M;
      c[i][j] %= M;
    }
}
int main() {
  long long i, a, d = 0, cnt;
  long long ans[2][2], tmp[2][2], mat[2][2];
  scanf("%I64d%I64d%I64d%I64d", &M, &L, &R, &K);
  L--;
  for (i = 1; i < R; i++) {
    a = R / (R / i);
    if (i <= L) chkmin(a, L / (L / i));
    if (R / a - L / a >= K) chkmax(d, a);
    i = a;
  }
  d--;
  mat[0][0] = mat[0][1] = mat[1][0] = 1 % M;
  mat[1][1] = 0;
  ans[0][0] = ans[1][1] = 1 % M;
  ans[1][0] = ans[0][1] = 0;
  for (int i = 0; i < 40; i++) {
    if (d & (1LL << i)) {
      multi(ans, mat, tmp);
      memcpy(ans, tmp, sizeof(ans));
    }
    multi(mat, mat, tmp);
    memcpy(mat, tmp, sizeof(mat));
  }
  printf("%I64d\n", ans[0][0]);
  return 0;
}
