#include <bits/stdc++.h>
using namespace std;
unsigned long long fnd(unsigned long long L, unsigned long long R,
                       unsigned long long K) {
  unsigned long long besta = 0;
  L--;
  for (unsigned long long a = 1; a <= 1000000; a++)
    if (R / a - L / a >= K) besta = a;
  for (unsigned long long p = K; p <= 1000000; p++) {
    unsigned long long a = R / p;
    if (a > besta && R / a - L / a >= K) besta = a;
  }
  return besta;
}
void matmult(unsigned long long a[][2], unsigned long long b[][2],
             unsigned long long c[][2], unsigned long long M) {
  unsigned long long 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]);
        c[i][j] = c[i][j] % M;
      }
    }
  }
}
void matpow(unsigned long long Z[][2], unsigned long long n,
            unsigned long long ans[][2], unsigned long long M) {
  unsigned long long temp[2][2];
  ans[0][0] = 1;
  ans[1][0] = 0;
  ans[0][1] = 0;
  ans[1][1] = 1;
  unsigned long long i, j;
  while (n > 0) {
    if (n & 1) {
      matmult(ans, Z, temp, M);
      for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++) ans[i][j] = temp[i][j];
    }
    matmult(Z, Z, temp, M);
    for (i = 0; i < 2; i++)
      for (j = 0; j < 2; j++) Z[i][j] = temp[i][j];
    n = n / 2;
  }
  return;
}
unsigned long long findFibonacci(unsigned long long n, unsigned long long M) {
  unsigned long long fib;
  if (n > 2) {
    unsigned long long Z[2][2] = {{1, 1}, {1, 0}}, result[2][2];
    matpow(Z, n - 2, result, M);
    fib = result[0][0] * 1 + result[0][1] * 0;
  } else
    fib = n - 1;
  return fib;
}
int main() {
  unsigned long long m, l, r, k;
  cin >> m >> l >> r >> k;
  unsigned long long g = fnd(l, r, k);
  unsigned long long ans = findFibonacci(g + 1, m);
  ans %= m;
  cout << ans << endl;
}
