#include <bits/stdc++.h>
using namespace std;
const long long oo = 1e9 + 7LL;
long long m, l, r, k;
struct matrix {
  vector<vector<long long> > M;
  vector<long long>& operator[](long long x) { return M[x]; };
  long long size() { return M.size(); }
  matrix(long long n, long long m) {
    M.assign(n + 1, vector<long long>(m + 1, 0LL));
  }
};
matrix operator*(matrix a, matrix b) {
  long long xa = a.size() - 1LL, ya = a[0].size() - 1LL;
  long long xb = b.size() - 1LL, yb = b[0].size() - 1LL;
  matrix res = matrix(xa, yb);
  for (long long i = 1; i <= xa; ++i) {
    for (long long j = 1; j <= yb; ++j) {
      long long cur = 0;
      for (long long k = 1LL; k <= xb; ++k) {
        cur = (cur + ((a[i][k] % m) * (b[k][j] % m))) % m;
      }
      res[i][j] = cur;
    }
  }
  return res;
}
matrix pow(matrix a, long long n) {
  long long A = a.size() - 1LL;
  matrix res = matrix(A, A), tmp = a;
  for (long long i = 1LL; i <= A; ++i) {
    for (long long j = 1LL; j <= A; ++j) {
      if (i == j)
        res[i][j] = 1LL;
      else
        res[i][j] = 0LL;
    }
  }
  for (long long i = 0LL; (1LL << i) <= n; ++i) {
    if (n & (1LL << i)) res = res * tmp;
    tmp = tmp * tmp;
  }
  return res;
}
long long fib(long long picked) {
  matrix tmp = matrix(2LL, 2LL);
  tmp[1][1] = 1LL;
  tmp[1][2] = 1LL;
  tmp[2][1] = 1LL;
  tmp[2][2] = 0LL;
  matrix res = matrix(1LL, 2LL);
  res[1][1] = 1LL;
  res[1][2] = 1LL;
  matrix mat = matrix(2LL, 2LL);
  mat = pow(tmp, picked - 1LL);
  res = res * mat;
  return (res[1][2] % m);
}
vector<long long> dif_pos;
int main() {
  ios_base::sync_with_stdio(false);
  scanf("%lld %lld %lld %lld", &m, &l, &r, &k);
  long long res = 0LL;
  for (long long i = 1; i * i <= r; ++i) {
    long long cur = r / i;
    dif_pos.push_back(i);
    dif_pos.push_back(cur);
  }
  for (long long i = 0LL; i < dif_pos.size(); ++i) {
    long long d_b = l / dif_pos[i] + 1LL * (l % dif_pos[i] != 0LL);
    long long u_b = r / dif_pos[i];
    if (u_b - d_b + 1 >= k) res = max(res, dif_pos[i]);
  }
  printf("%lld\n", fib(res));
}
