#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long mod, l, r, k;
void mul(long long a[2][2], long long b[2][2]) {
  long long res[2][2] = {{0}};
  int i, j, k;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++)
      for (k = 0; k < 2; k++) {
        res[i][j] = (res[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
      }
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) a[i][j] = res[i][j];
}
void power(long long a[2][2], long long n, long long res[2][2]) {
  int i, j;
  for (i = 0; i < 2; i++)
    for (j = 0; j < 2; j++) res[i][j] = (i == j);
  while (n > 0) {
    if (n % 2 == 0) {
      mul(a, a);
      n /= 2;
    } else {
      mul(res, a);
      n--;
    }
  }
}
long long fib(long long n) {
  if (n == 0) return 0;
  if (n <= 2) return 1;
  long long M[][2] = {1, 1, 1, 0};
  long long ans[2][2];
  power(M, n - 1, ans);
  long long x[][2] = {{1, 0}, {0, 0}};
  int i, j;
  mul(ans, x);
  return ans[0][0];
}
long long calc(long long val) { return (r / val) - ((l - 1) / val); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> mod >> l >> r >> k;
  if (mod == 1) {
    cout << "0";
    return 0;
  }
  long long ans = 1;
  for (long long x = 1; x * x <= r; x++) {
    if (calc(x) >= k) ans = max(ans, x);
    if (calc(r / x) >= k) ans = max(ans, r / x);
  }
  cout << fib(ans);
  return 0;
}
