#include <bits/stdc++.h>
const double pi = acos(-1.0);
using namespace std;
long long l, r, k, m;
long long mod;
struct Matrix {
  long long a[2][2];
  void init() { memset(a, 0, sizeof(a)); }
  void one() {
    init();
    for (int i = 0; i < 2; i++) a[i][i] = 1;
  }
  friend Matrix operator*(const Matrix& a, const Matrix& b) {
    Matrix ret;
    ret.init();
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          ret.a[i][j] += a.a[i][k] * b.a[k][j];
          ret.a[i][j] %= mod;
        }
      }
    }
    return ret;
  }
} MA, MB;
Matrix power(Matrix n, long long L) {
  Matrix ret;
  ret.one();
  while (L) {
    if (L & 1) ret = ret * n;
    n = n * n;
    L >>= 1;
  }
  return ret;
}
long long get_more() {
  long long d = (r - l) / (k - 1);
  while (d > 1) {
    if ((r / d - (l - 1) / d) >= k) return d;
    long long n = r / d + 1;
    d -= (n * d - r + (n - 1)) / n;
  }
  return 1;
}
int main() {
  cin >> m >> l >> r >> k;
  long long more = get_more();
  mod = m;
  MA.a[0][0] = 1;
  MA.a[0][1] = 1;
  MA.a[1][0] = 1;
  MA.a[1][1] = 0;
  if (more <= 2) {
    printf("%d\n", 1 % m);
    return 0;
  }
  MB = power(MA, more - 2);
  long long ans = (MB.a[0][0] + MB.a[1][0]) % m;
  cout << ans << endl;
}
