#include <bits/stdc++.h>
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (((a * b) / gcd(a, b))); }
long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
long long binpow(long long a, long long n, long long c) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= a;
    res %= c;
    a *= a;
    a %= c;
    n >>= 1;
  }
  res = (res + c) % c;
  return res;
}
void nxi(long long& n) {
  bool min = 0;
  char c;
  n = 0;
  while ((c = getc(stdin)) && c <= 32)
    ;
  if (c == '-')
    min = 1;
  else
    n = c - 48;
  while ((c = getc(stdin)) && c > 32) n = (n << 3) + (n << 1) + c - 48;
  if (min) n = -n;
}
void prl(long long n) {
  if (n == 0) {
    puts("0");
    return;
  }
  if (n < 0) {
    putchar('-');
    n = -n;
  }
  static long long s[10];
  long long top = 0;
  while (n > 0) s[top++] = n % 10, n /= 10;
  while (top--) putchar(s[top] + 48);
  puts("");
}
using namespace std;
const int nmax = 110;
long long M, l, r, k;
bool ok(long long l, long long r, long long q, long long k) {
  return (r / q) - (l + q - 1) / q + 1 >= k;
}
vector<vector<long long> > mul(vector<vector<long long> > a,
                               vector<vector<long long> > b) {
  vector<vector<long long> > ans;
  ans.resize(2);
  ans[0].resize(2);
  ans[1].resize(2);
  for (int i = 0; i < a.size(); i++)
    for (int j = 0; j < a[i].size(); j++)
      for (int p = 0; p < b[j].size(); p++)
        ans[i][p] = (ans[i][p] + 1ll * a[i][j] * b[j][p]) % M;
  return ans;
}
vector<vector<long long> > power(vector<vector<long long> > a, long long b) {
  if (b == 1)
    return a;
  else if (b & 1) {
    vector<vector<long long> > x = power(a, b - 1);
    x = mul(x, a);
    return x;
  } else {
    vector<vector<long long> > x = power(a, b / 2);
    x = mul(x, x);
    return x;
  }
}
long long F(long long pos) {
  if (pos == 1) return 1;
  vector<vector<long long> > m;
  m.resize(2);
  m[0].push_back(1);
  m[0].push_back(1);
  m[1].push_back(1);
  m[1].push_back(0);
  m = power(m, pos - 1);
  return m[0][0] % M;
}
int main() {
  cin >> M >> l >> r >> k;
  long long ans = 0;
  for (long long i = 1; i * i <= r; i++) {
    if (ok(l, r, i, k)) ans = max(ans, i);
    if (ok(l, r, r / i, k)) ans = max(ans, r / i);
  }
  cout << (F(ans) + M) % M << endl;
  return 0;
}
