#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
long long mo;
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
long long l, m, r, k, n;
long long ans, tmp;
long long find(long long mid) {
  if ((r / mid) - ((l - 1) / mid) >= k) return 1;
  return 0;
}
struct node {
  long long n, m, a[7][7];
  void init() {
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; i++) a[i][i] = 1;
  }
};
node mul(node aa, node bb, long long n, long long m, long long k) {
  node cc;
  cc.n = n;
  cc.m = k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      long long x = 0;
      for (int k = 0; k < m; k++) {
        x += aa.a[i][k] * bb.a[k][j] % mo;
        x = (x + mo) % mo;
      }
      cc.a[i][j] = x;
    }
  }
  return cc;
}
node power(node a, long long m) {
  node d;
  d.n = d.m = a.n;
  d.init();
  while (m) {
    if (m & 1) d = mul(d, a, d.n, d.m, a.m);
    m >>= 1;
    a = mul(a, a, a.n, a.n, a.n);
  }
  return d;
}
long long poww(long long a, long long n) {
  long long sum = 1;
  while (n) {
    if (n & 1) sum = sum * a % mo;
    n >>= 1;
    a = a * a % mo;
  }
  return sum;
}
int main() {
  int T, cas = 1;
  scanf("%lld%lld%lld%lld", &m, &l, &r, &k);
  long long lx = 1, rx = r + 1, as = 1;
  mo = m;
  for (long long i = 1; i * i <= r; i++) {
    if (find(i)) as = max(as, i);
    if (find((r / i))) as = max(as, (r / i));
  }
  if (as <= 2)
    printf("%lld\n", 1LL % mo);
  else {
    n = as;
    node x;
    x.n = 2;
    x.m = 2;
    memset(x.a, 0, sizeof(x.a));
    x.a[0][0] = 1;
    x.a[0][1] = 1;
    x.a[1][0] = 1;
    x.a[1][1] = 0;
    node ans = power(x, n - 2);
    node tmp;
    tmp.n = 2;
    tmp.m = 1;
    memset(tmp.a, 0, sizeof(tmp.a));
    tmp.a[0][0] = 1;
    tmp.a[1][0] = 1;
    ans = mul(ans, tmp, 2, 2, 1);
    long long sum = (ans.a[0][0] + mo) % mo;
    printf("%lld\n", sum);
  }
  return 0;
}
