#include <bits/stdc++.h>
using namespace std;
long long MOD, l, r, k;
void umn(long long a[2][2], long long b[2][2]) {
  long long tmp[2][2];
  memset(tmp, 0, sizeof tmp);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++)
        tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;
    }
  }
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) a[i][j] = tmp[i][j];
  }
}
long long fib(long long x) {
  if (x <= 2) return 1 % MOD;
  long long tmp[2][2];
  tmp[0][0] = 0;
  tmp[0][1] = 1;
  tmp[1][0] = 1;
  tmp[1][1] = 1;
  long long ans[2][2];
  ans[0][0] = 1;
  ans[0][1] = 0;
  ans[1][0] = 0;
  ans[1][1] = 1;
  x -= 2;
  while (x) {
    if (x & 1) umn(ans, tmp);
    umn(tmp, tmp);
    x >>= 1;
  }
  return (ans[1][0] + ans[1][1]) % MOD;
}
int main() {
  cin >> MOD >> l >> r >> k;
  l--;
  long long dmax = (r - l - 1) / (k - 1);
  while (r / dmax - l / dmax < k) {
    if (dmax < 1e6)
      dmax--;
    else
      dmax = r / (r / dmax + 1);
  }
  cout << fib(dmax) << endl;
  return 0;
}
