#include <bits/stdc++.h>
const int MOD = 1E9 + 7;
const int N = 50 + 5;
const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
using namespace std;
int n = 35;
long long mod, l, r, k;
struct Matrix {
  long long s[N][N];
  Matrix() { memset(s, 0, sizeof(s)); }
} E;
Matrix mul(Matrix A, Matrix B) {
  Matrix temp;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        temp.s[i][j] = (temp.s[i][j] + (A.s[i][k] * B.s[k][j]) % mod) % mod;
  return temp;
}
Matrix quickPow(Matrix A, long long k) {
  Matrix res = E;
  while (k) {
    if (k & 1) res = mul(res, A);
    A = mul(A, A);
    k >>= 1;
  }
  return res;
}
void init() {
  for (int i = 0; i < n; i++) E.s[i][i] = 1;
}
int main() {
  init();
  scanf("%lld%lld%lld%lld", &mod, &l, &r, &k);
  long long res = 0;
  for (long long i = 1; i * i <= r; i++) {
    if (r / i - (l - 1) / i >= k) res = max(res, i);
    if (r / (r / i) - (l - 1) / (r / i) >= k) res = max(res, r / i);
  }
  if (res == 1) {
    res = 1 % mod;
    printf("%lld", res);
  } else if (res == 2) {
    res = 1 % mod;
    printf("%lld", res);
  } else {
    Matrix A;
    A.s[0][0] = 1;
    A.s[0][1] = 1;
    A.s[1][0] = 1;
    A.s[1][1] = 0;
    Matrix B = quickPow(A, res - 2);
    printf("%lld", (B.s[0][0] + B.s[0][1]) % mod);
  }
  return 0;
}
