#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
void inc(long long &x, long long y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
struct Mat {
  static const int N = 2;
  long long a[N][N];
  void init(int x) {
    for (int i = (0); i < (N); ++i)
      for (int j = (0); j < (N); ++j) a[i][j] = (i == j ? x % MOD : 0);
  }
  Mat operator*(const Mat &p) {
    Mat ret;
    ret.init(0);
    for (int i = (0); i < (N); ++i)
      for (int j = (0); j < (N); ++j)
        for (int k = (0); k < (N); ++k)
          inc(ret.a[i][j], 1ll * a[i][k] * p.a[k][j] % MOD);
    return ret;
  }
  Mat operator^(long long b) {
    Mat ret, a = *this;
    ret.init(1);
    while (b > 0) {
      if (b & 1) ret = ret * a;
      a = a * a, b >>= 1;
    }
    return ret;
  }
} A;
long long solve(long long n) {
  A.a[0][0] = 1 % MOD, A.a[0][1] = 1 % MOD;
  A.a[1][0] = 1 % MOD, A.a[1][1] = 0;
  A = A ^ (n - 1);
  return A.a[0][0] % MOD;
}
long long calc(long long x, long long l, long long r) {
  if (x <= 0) return -1;
  return r / x - (l - 1) / x;
}
int main() {
  long long m, l, r, k;
  scanf("%lld%lld%lld%lld", &m, &l, &r, &k), MOD = m;
  long long p = 1;
  for (long long i = 1; i * i <= r; ++i) {
    if (calc(i, l, r) >= k) p = max(p, i);
    if (calc(r / i, l, r) >= k) p = max(p, r / i);
  }
  printf("%lld\n", solve(p));
  return 0;
}
