#include <bits/stdc++.h>
const int N = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
long long m, l, r, k;
long long a[2][2];
void multi(long long a[2][2], long long b[2][2]) {
  long long c[2][2];
  memset(c, 0, sizeof(c));
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++) c[i][j] += a[i][k] * b[k][j], c[i][j] %= m;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) a[i][j] = c[i][j];
}
void pow(long long a[2][2], long long n) {
  long long ret[2][2];
  ret[0][0] = ret[1][1] = 1;
  ret[0][1] = ret[1][0] = 0;
  while (n) {
    if (n & 1) multi(ret, a);
    multi(a, a);
    n >>= 1;
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) a[i][j] = ret[i][j];
}
void out(long long a[2][2]) {
  for (int i = 0; i < 2; i++, cout << endl)
    for (int j = 0; j < 2; j++) cout << a[i][j] << " ";
}
long long check(long long x, long long i) {
  long long l = 1, r = x, ret = x / i;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (x / mid >= i)
      ret = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ret;
}
int main() {
  cin >> m >> l >> r >> k;
  vector<long long> vt;
  for (long long i = 1, t; t = check(r, i), i <= t; i++) {
    vt.push_back(i);
    vt.push_back(t);
  }
  long long ret = 0;
  sort(vt.begin(), vt.end());
  for (int i = 0; i < ((vt).size()); i++)
    if (r / vt[i] - (l - 1) / vt[i] >= k) ret = vt[i];
  a[0][0] = a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 0;
  pow(a, ret);
  cout << a[1][0] << endl;
  return 0;
}
