#include <bits/stdc++.h>
const double PI = acos(-1.0);
using namespace std;
long long mod, l, r, k;
struct matrix {
  long long num[2][2];
  matrix() {
    num[0][0] = num[1][1] = 1;
    num[0][1] = num[1][0] = 0;
  }
};
matrix mul(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      c.num[i][j] = 0;
      for (int k = 0; k < 2; k++)
        c.num[i][j] =
            (c.num[i][j] % mod + a.num[i][k] % mod * b.num[k][j] % mod) % mod;
      c.num[i][j] %= mod;
    }
  return c;
}
matrix quick_pow(matrix a, long long x) {
  matrix t;
  t.num[1][1] = t.num[0][0] = 1;
  for (; x; x >>= 1) {
    if (x & 1) t = mul(t, a);
    a = mul(a, a);
  }
  return t;
}
long long maxx(long long a, long long b) {
  if (a > b) return a;
  return b;
}
int main() {
  long long k, l, r;
  cin >> mod >> l >> r >> k;
  long long ans = -1;
  for (long long int i = 1; i * i <= r; i++) {
    if (r / i - (l - 1) / i >= k) ans = maxx(ans, i);
    if (r / (r / i) - (l - 1) / (r / i) >= k) ans = maxx(ans, r / i);
  }
  if (mod == 1)
    cout << 0 << endl;
  else if (ans <= 2)
    cout << 1 << endl;
  else {
    matrix t;
    t.num[0][0] = t.num[1][0] = t.num[0][1] = 1;
    t.num[1][1] = 0;
    t = quick_pow(t, ans - 1);
    printf("%I64d\n", (t.num[0][0] + mod) % mod);
  }
  return 0;
}
