#include <bits/stdc++.h>
using namespace std;
int P;
struct Mat {
  unsigned long long mat[2][2];
  Mat operator*(Mat mm) {
    Mat ret;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) {
        unsigned long long &w = ret.mat[i][j];
        w = 0;
        for (int k = 0; k < 2; ++k) w = (w + mat[i][k] * mm.mat[k][j]) % P;
      }
    return ret;
  }
  Mat pow(unsigned long long k) {
    Mat ret = *this, a = *this;
    --k;
    while (k) {
      if (k & 1) ret = ret * a;
      a = a * a;
      k >>= 1;
    }
    return ret;
  }
};
int F(unsigned long long k, int m) {
  if (k <= 2) return 1 % m;
  P = m;
  Mat mm;
  mm.mat[0][0] = mm.mat[0][1] = mm.mat[1][0] = 1;
  mm.mat[1][1] = 0;
  mm = mm.pow(k - 2);
  return (mm.mat[0][0] + mm.mat[0][1]) % P;
}
int main() {
  int m;
  unsigned long long l, r, k;
  while (cin >> m >> l >> r >> k) {
    unsigned long long ans = 0;
    for (unsigned long long d = 1; d * d <= r; ++d) {
      unsigned long long a = r / d;
      unsigned long long lo = (a - k + 1) * d, hi = a * d;
      if (lo >= l && lo <= hi && hi <= r) ans = max(ans, d);
    }
    for (unsigned long long a = 1; a * a <= r; ++a) {
      unsigned long long d = r / (a + k - 1);
      if (a * d >= l) {
        ans = max(ans, d);
      }
    }
    cout << F(ans, m) << endl;
  }
  return 0;
}
