#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& x) {
  bool fu = 0;
  char c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') fu = 1, c = getchar();
  for (x = 0; c > 32; c = getchar()) x = x * 10 + c - '0';
  if (fu) x = -x;
};
template <class T>
inline void read(T& x, T& y) {
  read(x);
  read(y);
}
template <class T>
inline void read(T& x, T& y, T& z) {
  read(x);
  read(y);
  read(z);
}
inline char getc() {
  char c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  return c;
}
struct mat {
  int s[2][2];
} G, E, T;
long long mod, l, r, k, i, j, L, R, x, p;
mat operator*(mat a, mat b) {
  mat c;
  int i, j, k;
  for (i = 0; i <= 1; i++)
    for (j = 0; j <= 1; j++) {
      c.s[i][j] = 0;
      for (k = 0; k <= 1; k++)
        c.s[i][j] = (c.s[i][j] + 1LL * a.s[i][k] * b.s[k][j]) % mod;
    }
  return c;
}
mat operator^(mat a, long long x) {
  mat ans = E;
  for (; x; x >>= 1, a = a * a)
    if (x & 1) ans = ans * a;
  return ans;
}
long long get(long long a) {
  G.s[0][0] = G.s[0][1] = G.s[1][0] = 1;
  E.s[0][0] = E.s[1][1] = 1;
  G = G ^ a;
  return G.s[1][0];
}
int main() {
  cin >> mod;
  cin >> l >> r >> k;
  long long i, j, ans = 0;
  for (i = 1; i * i <= r; i++) {
    j = r / i;
    if (r / i - (l - 1) / i >= k) ans = max(ans, i);
    if (r / j - (l - 1) / j >= k) ans = max(ans, j);
  }
  cout << get(ans) % mod << endl;
  scanf("\n");
  return 0;
}
