#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000007;
const long long int inf = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;
const double PI = acos(-1);
long long int i, j, k;
void solve(void);
inline bool equal(double a, double b) { return fabs(a - b) < eps; }
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 m;
unordered_map<long long int, long long int> f;
long long int fib(long long int n) {
  if (n == 0) return 0;
  if (n == 1 || n == 2) return (f[n] = 1) % m;
  if (f[n]) return f[n];
  long long int k = (n & 1) ? (n + 1) / 2 : n / 2;
  f[n] = (n & 1) ? ((fib(k) * fib(k)) % m + (fib(k - 1) * fib(k - 1)) % m) % m
                 : (((2 * fib(k - 1)) % m + fib(k)) % m * fib(k)) % m;
  return f[n];
}
void solve() {
  long long int l, r, k;
  cin >> m >> l >> r >> k;
  long long int d = (r - l) / (k - 1);
  while (d > 1) {
    if (1 + r / d - (l + d - 1) / d >= k) break;
    long long int N = 1 + r / d;
    d -= ((N * d - r) + (N - 1)) / N;
  }
  cout << fib(d) << '\n';
}
