#include <bits/stdc++.h>
#pragma comment(linker, "/stack:100000000")
using namespace std;
long long M[2][2] = {{1, 1}, {1, 0}};
long long A[62][55][55];
long long B[55][55];
long long C[55][55];
long long MOD;
const int m = 2;
long long solve(long long n) {
  memset(A, 0, sizeof(A));
  for (int(i) = 0; (i) < (m); (i)++)
    for (int(j) = 0; (j) < (m); (j)++) A[0][i][j] = M[i][j];
  for (int p = 1; p < 62; p++) {
    for (int(i) = 0; (i) < (m); (i)++)
      for (int(j) = 0; (j) < (m); (j)++)
        for (int(k) = 0; (k) < (m); (k)++) {
          A[p][i][j] += A[p - 1][i][k] * A[p - 1][k][j];
          A[p][i][j] %= MOD;
        }
  }
  memset(B, 0, sizeof(B));
  for (int(i) = 0; (i) < (m); (i)++) B[i][i] = 1;
  long long mask = n - 1;
  for (int(p) = 0; (p) < (62); (p)++) {
    if (mask & (1LL << p)) {
      memset(C, 0, sizeof(C));
      for (int(i) = 0; (i) < (m); (i)++)
        for (int(j) = 0; (j) < (m); (j)++)
          for (int(k) = 0; (k) < (m); (k)++) {
            C[i][j] += B[i][k] * A[p][k][j];
            C[i][j] %= MOD;
          }
      memcpy(B, C, sizeof(C));
    }
  }
  long long res = B[0][0] % MOD;
  return res;
}
long long best = 1, L, R, K;
long long F(long long x) { return R / x - (L - 1) / x; }
void check(long long x) {
  if (F(x) >= K && x > best) best = x;
}
int main() {
  cin >> MOD >> L >> R >> K;
  for (int i = 1; i <= (R < 2000000 ? R : 2000000); i++) {
    check(i);
    check(R / i);
  }
  cout << solve(best) << "\n";
  return 0;
}
