#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k;
unsigned long long a[2][2], b[2][2], c[2][2];
void pow(long long x) {
  if (x == 0) return;
  pow(x / 2);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      c[i][j] = 0;
      for (int k = 0; k < 2; k++)
        c[i][j] = (c[i][j] + b[i][k] * b[k][j] % m) % m;
    }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) b[i][j] = c[i][j];
  if (x % 2 == 1) {
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        c[i][j] = 0;
        for (int k = 0; k < 2; k++)
          c[i][j] = (c[i][j] + b[i][k] * a[k][j] % m) % m;
      }
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) b[i][j] = c[i][j];
  }
}
int main() {
  scanf("%I64d%I64d%I64d%I64d", &m, &l, &r, &k);
  long long ans = 1;
  for (long long L = 1; L <= max(r, l); L++) {
    long long j = r / L - (l - 1) / L;
    if (L <= l - 1)
      L = min(r / (r / L), ((l - 1) / ((l - 1) / L)));
    else
      L = r / (r / L);
    if (j >= k) ans = L;
  }
  a[0][0] = a[0][1] = a[1][0] = 1;
  b[0][0] = b[1][1] = 1;
  if (ans > 2) {
    pow(ans - 2);
    printf("%I64d\n", (b[0][0] + b[1][0]) % m);
  } else
    printf("%I64d\n", 1LL % m);
  return 0;
}
