#include <bits/stdc++.h>
using namespace std;
long long m, a, b, k;
struct oo {
  long long t[2][2];
};
oo su;
oo tt;
oo cheng(oo x, oo y) {
  oo ans;
  for (int i = 0; i <= 1; i++) {
    for (int j = 0; j <= 1; j++) {
      ans.t[i][j] = 0;
      for (int k = 0; k <= 1; k++) {
        ans.t[i][j] += x.t[i][k] * y.t[k][j];
        ans.t[i][j] %= m;
      }
    }
  }
  return ans;
}
oo kpow(long long x) {
  if (x == 0) return su;
  oo ans = kpow(x / 2);
  ans = cheng(ans, ans);
  if (x % 2) ans = cheng(ans, tt);
  return ans;
}
long long ff(long long x) {
  su.t[0][1] = 0;
  su.t[0][0] = 1;
  su.t[1][0] = 0;
  su.t[1][1] = 1;
  tt.t[0][0] = 0;
  tt.t[0][1] = 1;
  tt.t[1][0] = 1;
  tt.t[1][1] = 1;
  if (x == 1) return 1 % m;
  oo p = kpow(x - 2);
  long long ans = p.t[0][1] + p.t[1][1];
  ans %= m;
  return ans;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d", &m, &b, &a, &k);
  long long ans = 0, pos;
  pos = a / k;
  while (pos >= 1) {
    long long pp = a / pos - (b - 1) / pos;
    if (pp >= k) ans = max(pos, ans);
    pos = a / (a / pos + 1);
  }
  printf("%I64d", ff(ans));
  return 0;
}
