#include <bits/stdc++.h>
using namespace std;
typedef struct {
  int m[2][2];
} Matrix;
Matrix I = {
    1,
    0,
    0,
    1,
};
long long m, l, r, k;
Matrix matrixmul(Matrix a, Matrix b) {
  int i, j, k;
  Matrix c;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) {
      c.m[i][j] = 0;
      for (k = 0; k < 2; k++) c.m[i][j] += (a.m[i][k] % m * b.m[k][j] % m) % m;
      c.m[i][j] %= m;
    }
  return c;
}
Matrix quickpow(long long n, Matrix m) {
  Matrix b = I;
  while (n >= 1) {
    if (n & 1) b = matrixmul(b, m);
    n = n >> 1;
    m = matrixmul(m, m);
  }
  return b;
}
long long solve() {
  long long ans = 0;
  long long temp = sqrt(r);
  long long i;
  long long tmp;
  for (i = 1; i <= temp; ++i) {
    if (r / i - (l - 1) / i >= k) ans = max(ans, i);
    tmp = r / i;
    if (r / tmp - (l - 1) / tmp >= k) ans = max(ans, tmp);
  }
  return ans;
}
int main() {
  cin >> m >> l >> r >> k;
  Matrix init = {
      1,
      1,
      1,
      0,
  };
  long long num = solve();
  init = quickpow(num - 1, init);
  cout << init.m[0][0] % m << "\n";
  return 0;
}
