#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  long long X00, X01, X10, X11;
};
int Mod;
Matrix operator*(Matrix A, Matrix B) {
  Matrix Ans;
  Ans.X00 = (A.X00 * B.X00 + A.X01 * B.X10) % Mod;
  Ans.X01 = (A.X00 * B.X01 + A.X01 * B.X11) % Mod;
  Ans.X10 = (A.X10 * B.X00 + A.X11 * B.X10) % Mod;
  Ans.X11 = (A.X10 * B.X01 + A.X11 * B.X11) % Mod;
  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() {
  long long L, R, K, N = 0;
  cin >> Mod >> L >> R >> K;
  L--;
  for (long long i = 1; i * i <= R; i++) {
    if (R / i - L / i >= K) N = max(N, i);
    if (L / i)
      if (R / (L / i) - L / (L / i) >= K) N = max(N, (L / i));
    if (R / (R / i) - L / (R / i) >= K) N = max(N, (R / i));
  }
  cout << ((Matrix){0, 1 % Mod, 1 % Mod, 1 % Mod} ^ N).X10 << endl;
  return 0;
}
