#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:255000000")
bool firstout = 1;
template <class T>
T &minn(T &a, T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
T &maxx(T &a, T b) {
  if (a < b) a = b;
  return a;
}
int mod;
int &madd(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int &msub(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
int &mmult(int &a, int b) { return a = (long long)a * b % mod; }
int mdiv(long long a, long long b, long long m) {
  a = (a % m + m) % m;
  b = (b % m + m) % m;
  if (a % b == 0) return a / b;
  return (a + m * mdiv(-a, m, b)) / b;
}
int n, m, q;
int O[2][2], A[2][2];
void mult(int A[2][2], int B[2][2], int CC[2][2]) {
  int 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)
        madd(C[i][j], (long long)A[i][k] * B[k][j] % mod);
    }
  for (i = (0); i < (2); ++i)
    for (j = (0); j < (2); ++j) CC[i][j] = C[i][j];
}
int fib(long long x) {
  int i, j;
  for (i = (0); i < (2); ++i)
    for (j = (0); j < (2); ++j) O[i][j] = 1 % mod;
  O[0][0] = 0;
  for (i = (0); i < (2); ++i)
    for (j = (0); j < (2); ++j) A[i][j] = 0;
  for (i = (0); i < (2); ++i) A[i][i] = 1 % mod;
  for (; x; x >>= 1) {
    if (x & 1) mult(A, O, A);
    mult(O, O, O);
  }
  return A[0][1];
}
int main() {
  int i, j, k;
  char c;
  int a, d;
  int ts;
  for (ts = 1; scanf("%"
                     "d",
                     &(mod)) > 0;
       ++ts) {
    long long l, r, n;
    scanf(
        "%"
        "I64d",
        &(l));
    scanf(
        "%"
        "I64d",
        &(r));
    scanf(
        "%"
        "I64d",
        &(n));
    --n;
    long long res = 1;
    for (i = (2); i < (1012345); ++i)
      if ((l + i - 1) / i * i + n * i <= r) maxx(res, (long long)i);
    for (i = (1); i < (1012345); ++i) {
      long long x = r / (i + n);
      if (x * i >= l) maxx(res, x);
    }
    res = fib(res);
    printf(
        "%"
        "I64d",
        (res));
    printf("\n"), firstout = 1;
  }
  return 0;
}
