#include <bits/stdc++.h>
using namespace std;
long long m, L, R, K;
struct Matrix {
  long long x00, x01, x10, x11;
  Matrix() {}
  Matrix(long long x00, long long x01, long long x10, long long x11)
      : x00(x00), x01(x01), x10(x10), x11(x11) {}
};
Matrix operator*(Matrix A, Matrix B) {
  Matrix Ans;
  Ans.x00 = (A.x00 * B.x00 + A.x01 * B.x10) % m;
  Ans.x01 = (A.x00 * B.x01 + A.x01 * B.x11) % m;
  Ans.x10 = (A.x10 * B.x00 + A.x11 * B.x10) % m;
  Ans.x11 = (A.x10 * B.x10 + A.x11 * B.x11) % m;
  return Ans;
}
Matrix operator^(Matrix A, long long N) {
  if (N == 1) return A;
  Matrix T = (A * A) ^ (N / 2);
  if (N & 1) T = T * A;
  return T;
}
int main() {
  cin >> m >> L >> R >> K;
  L--;
  long long ret = -1;
  for (long long i = 1; i * i <= R; ++i) {
    if (R / i - L / i >= K) ret = max(ret, i);
    if (L / i)
      if (R / (L / i) - (L / (L / i)) >= K) ret = max(ret, L / i);
    if (R / i)
      if (R / (R / i) - (L / (R / i)) >= K) ret = max(ret, R / i);
  }
  Matrix H = Matrix(0, 1 % m, 1 % m, 1 % m);
  cout << (H ^ ret).x10 << endl;
  return 0;
}
