#include <bits/stdc++.h>
using namespace std;
long long mod, l, r, k;
long long MaxGcd() {
  long long maxx = 1;
  for (long long i = 2; i <= (long long)sqrt(r * 1.0); ++i) {
    if (r / i - (l - 1) / i >= k) maxx = max(maxx, i);
    long long another = r / i;
    if (r / another - (l - 1) / another >= k) maxx = max(maxx, another);
  }
  return maxx;
}
const int maxn = 3;
struct mat {
  long long m[maxn][maxn], n;
  mat(long long _Size) {
    memset(m, 0, sizeof m);
    n = _Size;
  }
  inline void set() {
    memset(m, 0, sizeof m);
    for (int i = 1; i <= n; ++i) m[i][i] = 1;
  }
  inline mat operator*(const mat &B) const {
    mat C = mat(n);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        for (int x = 1; x <= n; x++)
          C.m[i][j] = (C.m[i][j] + (m[i][x] * B.m[x][j]) % mod) % mod;
      }
    return C;
  }
  inline mat operator^(long long coun) {
    mat C = mat(n), A = *this;
    C.set();
    while (coun > 0) {
      if (coun & 1) C = C * A;
      A = A * A;
      coun >>= 1;
    }
    return C;
  }
};
int main() {
  while (cin >> mod >> l >> r >> k) {
    long long maxx = MaxGcd();
    mat A(2);
    A.m[1][1] = 1;
    A.m[1][2] = 1;
    A.m[2][1] = 1;
    A.m[2][2] = 0;
    A = A ^ (maxx - 1);
    mat B(2);
    B.m[1][1] = 1;
    B.m[1][2] = 0;
    B = B * A;
    printf("%lld\n", B.m[1][1]);
  }
  return 0;
}
