#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000007;
const long long int inf = 0x3f3f3f3f3f3f3f3fLL;
long long int i, j, k;
void solve(void);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int t = 1;
  while (t--) solve();
  return 0;
}
long long int mat[2][2], m;
void multiply(long long int a[2][2], long long int b[2][2]) {
  long long int res[2][2];
  memset(res, 0, sizeof(res));
  int i, j, k;
  for (i = (0); i <= (1); ++i)
    for (j = (0); j <= (1); ++j)
      for (k = (0); k <= (1); ++k) {
        res[i][j] += (a[i][k] * b[k][j]) % m;
        res[i][j] %= m;
      }
  for (i = (0); i <= (1); ++i)
    for (j = (0); j <= (1); ++j) a[i][j] = res[i][j];
}
void power(long long int a[2][2], long long int p) {
  long long int res[2][2];
  memset(res, 0, sizeof(res));
  res[0][0] = res[1][1] = 1;
  while (p > 0) {
    if (p & 1) multiply(res, a);
    p /= 2;
    multiply(a, a);
  }
  for (i = (0); i <= (1); ++i)
    for (j = (0); j <= (1); ++j) a[i][j] = res[i][j];
}
void solve() {
  long long int l, r, k;
  cin >> m >> l >> r >> k;
  long long int d = (r - l) / (k - 1);
  while (d > 0) {
    if (r / d - (l + d - 1) / d + 1 >= k) break;
    long long int N = (1 + r / d);
    d -= (N * d - r + N - 1) / N;
  }
  if (d <= 2)
    cout << 1 % m << '\n';
  else {
    mat[0][0] = mat[0][1] = mat[1][0] = 1;
    power(mat, d - 2);
    cout << (mat[0][0] + mat[0][1]) % m << '\n';
  }
}
