#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, LOG = 60;
int mod;
struct mat {
  int v[2][2];
  mat(int p = 0, int q = 1) {
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        if (i == j)
          v[i][j] = q;
        else
          v[i][j] = p;
  }
} fib(0, 1), adj(0, 0);
mat mul(mat &a, mat &b) {
  mat res(0, 0);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        res.v[i][j] += (1LL * a.v[i][k] * b.v[k][j]) % mod, res.v[i][j] %= mod;
  return res;
}
int main() {
  long long l, r, k;
  cin >> mod >> l >> r >> k;
  long long ans = -1;
  for (int i = 1; 1LL * i * i <= r; i++)
    if (r / i - (l - 1) / i >= k) ans = max(ans, 1LL * i);
  for (int i = k; 1LL * i * i <= r; i++) {
    long long mxs = r / i;
    if (i - (l - 1) / mxs >= k) ans = max(ans, mxs);
  }
  adj.v[0][0] = adj.v[0][1] = adj.v[1][0] = 1;
  adj.v[1][1] = 0;
  for (int j = 0; j < LOG; j++) {
    if (ans & (1LL << j)) fib = mul(fib, adj);
    adj = mul(adj, adj);
    if ((1LL << j) > ans) break;
  }
  cout << fib.v[1][0] << endl;
}
