#include <bits/stdc++.h>
using namespace std;
long long mod, l, r, k, ind = 1;
template <class mat_type>
struct matrix {
  int n_rows, n_cols;
  vector<vector<mat_type> > m;
  matrix(int r = 1, int c = 1, bool I = false) {
    m.resize(r);
    for (int i = 0; i < r; i++) m[i].resize(c, 0);
    n_rows = r;
    n_cols = c;
    if (I) make_identity();
  }
  void make_identity() {
    for (int i = 0; i < n_rows; i++) m[i][i] = 1;
  }
  mat_type add(mat_type a, mat_type b) { return (a + b) % mod; }
  mat_type sub(mat_type a, mat_type b) { return ((a - b) % mod + mod) % mod; }
  mat_type mul(mat_type a, mat_type b) { return (a * b) % mod; }
  matrix operator+(const matrix& other) {
    matrix ans(n_rows, n_cols);
    for (int i = 0; i < n_rows; i++)
      for (int j = 0; j < n_cols; j++)
        ans.m[i][j] = add(m[i][j], other.m[i][j]);
    return ans;
  }
  matrix operator-(const matrix& other) {
    matrix ans(n_rows, n_cols);
    for (int i = 0; i < n_rows; i++)
      for (int j = 0; j < n_cols; j++)
        ans.m[i][j] = sub(m[i][j], other.m[i][j]);
    return ans;
  }
  matrix operator*(const matrix& other) {
    matrix ans(n_rows, other.n_cols);
    for (int i = 0; i < n_rows; i++)
      for (int j = 0; j < other.n_cols; j++)
        for (int k = 0; k < n_cols; k++)
          ans.m[i][j] = add(ans.m[i][j], mul(m[i][k], other.m[k][j]));
    return ans;
  }
  matrix power(long long exp) {
    matrix ans(n_rows, n_cols, true);
    matrix multiplier = *this;
    while (exp > 0) {
      if (exp & 1) ans = ans * multiplier;
      exp >>= 1;
      multiplier = multiplier * multiplier;
    }
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> mod >> l >> r >> k;
  for (long long i = 1; (i * i) <= r; i++) {
    long long val = i;
    if (((r / val) - (l - 1) / val) >= k) ind = max(ind, val);
    val = r / i;
    if (((r / val) - (l - 1) / val) >= k) ind = max(ind, val);
    val = max((l - 1) / i, 1LL);
    if (((r / val) - (l - 1) / val) >= k) ind = max(ind, val);
  }
  ind--;
  matrix<long long> mt(2, 2);
  mt.m[0][0] = 1;
  mt.m[0][1] = 1;
  mt.m[1][0] = 1;
  mt.m[1][1] = 0;
  matrix<long long> p = mt.power(ind);
  cout << p.m[0][0] % mod;
  return 0;
}
