#include <bits/stdc++.h>
using namespace std;
long long i, j, k, l, m, n, a[123][456], b[123][456], c, d, e, s, t;
string p, q, r, w;
int main() {
  cin >> m >> c >> d >> k;
  e = 1;
  c--;
  for (i = 1; i * i <= d; i++) {
    if (d / i - c / i >= k) l = max(l, i);
    j = d / i;
    if (d / j - c / j >= k) l = max(l, j);
  }
  a[1][1] = 1;
  a[0][1] = 1;
  a[1][0] = 1;
  b[1][1] = 1;
  b[0][0] = 1;
  while (l > 0) {
    if (l % 2 == 1) {
      c = (b[1][1] * a[1][1] + b[1][0] * a[0][1]) % m;
      d = (b[1][1] * a[1][0] + b[1][0] * a[0][0]) % m;
      e = (b[0][1] * a[1][1] + b[0][0] * a[0][1]) % m;
      t = (b[0][1] * a[1][0] + b[0][0] * a[0][0]) % m;
      b[1][1] = c;
      b[1][0] = d;
      b[0][1] = e;
      b[0][0] = t;
    }
    c = (a[1][1] * a[1][1] + a[1][0] * a[0][1]) % m;
    d = (a[1][1] * a[1][0] + a[1][0] * a[0][0]) % m;
    e = (a[0][1] * a[1][1] + a[0][0] * a[0][1]) % m;
    t = (a[0][1] * a[1][0] + a[0][0] * a[0][0]) % m;
    a[1][1] = c;
    a[1][0] = d;
    a[0][1] = e;
    a[0][0] = t;
    l /= 2;
  }
  cout << b[1][0];
  return 0;
}
