#include <bits/stdc++.h>
using namespace std;
const int N = 110000;
long long mod, a[5][5], b[5][5], c[5][5];
vector<long long> t;
long long fib(long long x) {
  a[0][0] = 1;
  a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 0;
  b[0][0] = 1;
  b[0][1] = 0;
  b[1][0] = 0;
  b[1][1] = 1;
  while (x) {
    if (x & 1) {
      c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod;
      c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod;
      c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod;
      c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod;
      b[0][0] = c[0][0];
      b[0][1] = c[0][1];
      b[1][0] = c[1][0];
      b[1][1] = c[1][1];
    }
    c[0][0] = (a[0][0] * a[0][0] + a[0][1] * a[1][0]) % mod;
    c[0][1] = (a[0][0] * a[0][1] + a[0][1] * a[1][1]) % mod;
    c[1][0] = (a[1][0] * a[0][0] + a[1][1] * a[1][0]) % mod;
    c[1][1] = (a[1][0] * a[0][1] + a[1][1] * a[1][1]) % mod;
    a[0][0] = c[0][0];
    a[0][1] = c[0][1];
    a[1][0] = c[1][0];
    a[1][1] = c[1][1];
    x >>= 1;
  }
  return b[1][0];
}
long long l, r, k;
long long f(long long x) {
  if (x <= 0) return 0;
  if (r / x - (l - 1) / x >= k) return 1;
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> mod >> l >> r >> k;
  long long L = 1;
  for (int i = 1; i <= 1000000; i++) t.push_back(i);
  long long x = l / 1000000;
  while (x > 0) {
    x--;
    t.push_back((l - 1) / (x + 1) + 1);
  }
  x = r / 1000000;
  while (x > 0) {
    x--;
    t.push_back((r - 1) / (x + 1) + 1);
  }
  for (auto i : t) {
    for (long long j = -5; j <= 5; j++)
      if (f(i + j)) L = max(L, i + j);
  }
  cout << fib(L);
}
