#include <bits/stdc++.h>
using namespace std;
unsigned long long m, l, r, k, nr;
unsigned long long a[10][10];
unsigned long long sol[10][10], N, maxdiv, minus, plus;
unsigned long long maxdiff;
void inmu(unsigned long long a[][10], unsigned long long b[][10]) {
  unsigned long long c[10][10];
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= 2; ++j) c[i][j] = 0;
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= 2; ++j)
      for (int k = 1; k <= 2; ++k) {
        c[i][j] = (c[i][j] + ((1LL * a[i][k] * b[k][j]) % m)) % m;
      }
  for (int i = 1; i <= 2; ++i)
    for (int j = 1; j <= 2; ++j) {
      a[i][j] = c[i][j] % m;
    }
}
void power() {
  sol[1][1] = 1;
  sol[2][2] = 1;
  for (unsigned long long i = 0; 1LL * (1LL << i) <= N; ++i) {
    if ((1LL << i * 1LL) & N) {
      inmu(sol, a);
    }
    inmu(a, a);
  }
}
unsigned long long verif(unsigned long long div) {
  if (div > (r - l + 1)) return 0;
  unsigned long long mod, nr1, maxdiff1, prim;
  mod = r % div;
  prim = r - mod;
  nr1 = prim - l;
  maxdiff1 = 1LL * nr1 / (k - 1);
  if (maxdiff1 >= div)
    return 1;
  else
    return 0;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d", &m, &l, &r, &k);
  nr = r - l;
  maxdiff = 0;
  unsigned long long st = 1, q;
  unsigned long long dr = maxdiff;
  unsigned long long mij = 0;
  for (unsigned long long i = 1; i * i <= r; ++i) {
    if (verif(i)) maxdiff = max(maxdiff, i);
    if (verif(r / i)) maxdiff = max(maxdiff, r / i);
  }
  N = maxdiff;
  a[1][2] = 1;
  a[2][1] = 1;
  a[2][2] = 1;
  power();
  printf("%I64d", sol[1][2]);
  return 0;
}
