#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k, n;
long long a[2][2], b[2][2];
void cc(long long a[2][2], long long b[2][2]) {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) a[i][j] = b[i][j];
}
void mul(long long a[2][2], long long b[2][2], long long m) {
  long long c[2][2];
  memset(c, 0, sizeof(c));
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++) c[i][j] += a[i][k] * b[k][j], c[i][j] %= m;
  cc(a, c);
}
void mi(long long a[2][2], long long n, long long m) {
  long long y[2][2];
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) y[i][j] = 0;
  y[0][0] = 1;
  y[1][1] = 1;
  while (n > 0) {
    if (n % 2 == 1) mul(y, a, m);
    n = n / 2;
    mul(a, a, m);
  }
  cc(a, y);
}
int main() {
  cin >> m >> l >> r >> k;
  n = -1;
  for (long long i = k;; i++) {
    long long x = r / i;
    long long y = r / x;
    long long z = (l - 1) / x;
    if (x <= 1000000) break;
    if (y - z >= k) {
      n = x;
      break;
    }
  }
  if (n == -1)
    for (long long i = 1000000; i >= 1; i--) {
      long long y = r / i;
      long long z = (l - 1) / i;
      if (y - z >= k) {
        n = i;
        break;
      }
    }
  a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 1;
  b[0][1] = 1;
  b[0][0] = 1;
  mi(a, n - 2, m);
  mul(b, a, m);
  cout << b[0][1] << endl;
}
