#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using std::cerr;
using std::cin;
using std::cos;
using std::cout;
using std::endl;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::next_permutation;
using std::pair;
using std::priority_queue;
using std::queue;
using std::random_shuffle;
using std::set;
using std::sin;
using std::sort;
using std::sqrt;
using std::stack;
using std::string;
using std::stringstream;
using std::swap;
using std::vector;
const long double PI = 3.14159265358979323846;
const double eps = 1e-12;
int m;
vector<long long> pr(const vector<long long> a, const vector<long long> b) {
  vector<long long> res(4, 0);
  res[0] = (a[0] * b[0] + a[1] * b[2]) % m;
  res[1] = (a[0] * b[1] + a[1] * b[3]) % m;
  res[2] = (a[2] * b[0] + a[3] * b[2]) % m;
  res[3] = (a[2] * b[1] + a[3] * b[3]) % m;
  return res;
}
vector<long long> pow(vector<long long> matr, long long n) {
  vector<long long> res(4, 0);
  res[0] = res[2] = 1;
  while (n) {
    if (n & 1) res = pr(res, matr);
    matr = pr(matr, matr);
    n >>= 1;
  }
  return res;
}
int main() {
  long long l, r, k;
  cin >> m >> l >> r >> k;
  long long k1 = k;
  long long d;
  while ((k1 < 1e9) && (k1 * k1 < r)) {
    d = r / k1;
    if (d * (k1 - k + 1) >= l)
      break;
    else
      ++k1;
  }
  d = r / k1;
  while (true) {
    if (r / d - (l - 1) / d >= k)
      break;
    else
      --d;
  }
  vector<long long> matr(4, 1);
  matr[0] = 0;
  matr = pow(matr, d - 1);
  cout << (matr[0] + matr[1]) % m << endl;
  return 0;
}
