#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;
long long in() {
  long long r = 0, c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') return -in();
  for (; c > 32; r = (r << 1) + (r << 3) + c - '0', c = getchar())
    ;
  return r;
}
long long mat[2][2];
long long mat2[2][2];
long long aux[2][2];
long long func(long long l, long long r, long long k) {
  long long x;
  long long sr = max((long long)sqrt(r), 1LL);
  long long ans = 1;
  for (x = 1; x <= sr; x++) {
    if (r / x - (l + x - 1) / x + 1 >= k) ans = x;
  }
  for (x = 1; x <= r / sr; x++) {
    long long d = r / x;
    if (r / d - (l + d - 1) / d + 1 >= k) ans = max(ans, d);
  }
  return ans;
}
void solve() {
  long long M = in();
  long long l = in();
  long long r = in();
  long long k = in();
  mat[0][0] = 0;
  mat[0][1] = 1;
  mat[1][0] = 1;
  mat[1][1] = 1;
  mat2[0][0] = 1;
  mat2[0][1] = 0;
  mat2[1][0] = 0;
  mat2[1][1] = 1;
  int i, j;
  long long N = func(l, r, k);
  while (N) {
    if (N & 1) {
      for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++) aux[i][j] = mat2[i][j];
      mat2[0][0] = (aux[0][0] * mat[0][0] + aux[0][1] * mat[1][0]) % M;
      mat2[0][1] = (aux[0][0] * mat[0][1] + aux[0][1] * mat[1][1]) % M;
      mat2[1][0] = (aux[1][0] * mat[0][0] + aux[1][1] * mat[1][0]) % M;
      mat2[1][1] = (aux[1][0] * mat[0][1] + aux[1][1] * mat[1][1]) % M;
    }
    for (i = 0; i < 2; i++)
      for (j = 0; j < 2; j++) aux[i][j] = mat[i][j];
    mat[0][0] = (aux[0][0] * aux[0][0] + aux[0][1] * aux[1][0]) % M;
    mat[0][1] = (aux[0][0] * aux[0][1] + aux[0][1] * aux[1][1]) % M;
    mat[1][0] = (aux[1][0] * aux[0][0] + aux[1][1] * aux[1][0]) % M;
    mat[1][1] = (aux[1][0] * aux[0][1] + aux[1][1] * aux[1][1]) % M;
    N >>= 1;
  }
  cout << mat2[0][1] << endl;
}
int main() {
  solve();
  return 0;
}
