#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void input(T &x) {
  register char c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline long long bigmod(long long p, long long e, long long M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
const int MRows = 2;
const int MCols = 2;
long long MOD;
struct Matrix {
  int r, c;
  long long m[MRows][MCols];
  void init(int R, int C) {
    memset(m, 0, sizeof(m));
    r = R;
    c = C;
  }
  void iden() {
    for (int i = 0; i < r; i++) m[i][i] = 1;
  }
  void print() {
    puts("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
    for (int i = 0; i < r; ++i) {
      for (int j = 0; j < c; ++j) printf("%4d  ", m[i][j]);
      printf("\n");
    }
    puts("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
  }
  void mul(const Matrix &y, Matrix &z) const {
    z.r = r, z.c = y.c;
    long long v;
    for (int i = 0; i < z.r; ++i)
      for (int j = 0; j < z.c; ++j) {
        v = 0;
        for (int k = 0; k < c; ++k) {
          v += m[i][k] * y.m[k][j];
          v %= MOD;
        }
        z.m[i][j] = v;
      }
  }
  void add(const Matrix &B, Matrix &c) {
    c.r = c.c = r;
    for (int i = 0; i < c.r; i++) {
      for (int j = 0; j < c.c; j++) {
        c.m[i][j] = m[i][j] + B.m[i][j];
      }
    }
  }
  void exp(long long e, Matrix &z) {
    z.init(r, c);
    z.iden();
    Matrix x, b = *this;
    while (true) {
      if (e & 1) {
        z.mul(b, x);
        z = x;
      }
      e >>= 1;
      if (e == 0) break;
      b.mul(b, x);
      b = x;
    }
  }
};
const int N = 1001;
vector<long long> pivot;
void get(long long n) {
  long long sqN = sqrt(n);
  vector<pair<long long, long long> > ret;
  for (long long i = 1; i <= sqN; i++) {
    long long u = n / i, v = n / (i + 1) + 1;
    pivot.push_back(i);
    if (v > i) pivot.push_back(v), pivot.push_back(u);
  }
}
int main() {
  long long m, l, r, k;
  cin >> m >> l >> r >> k;
  get(r);
  get(l - 1);
  long long ans = 1;
  for (auto n : pivot) {
    long long now = r / n - (l - 1) / n;
    if (now >= k) ans = max(ans, n);
  }
  MOD = m;
  Matrix A, B;
  A.init(2, 2);
  A.m[0][0] = A.m[0][1] = A.m[1][0] = 1;
  A.m[1][1] = 0;
  A.exp(ans - 1, B);
  cout << B.m[0][0] % m << endl;
  return 0;
}
