#include <bits/stdc++.h>
using namespace std;
long long m, l, r, k;
long long res = 1;
struct matrix {
  vector<vector<long long> > a;
  matrix() { a.assign(2, vector<long long>(2, 0)); }
  matrix operator*(matrix b) {
    matrix c;
    c.a[0][0] = c.a[0][1] = c.a[1][0] = c.a[1][1] = 0;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) {
          c.a[i][j] += a[i][k] * b.a[k][j] % m;
          c.a[i][j] %= m;
        }
    return c;
  }
};
long long get_fib(long long x) {
  matrix b;
  b.a[0][0] = 1;
  b.a[0][1] = 1;
  b.a[1][0] = 1;
  b.a[1][1] = 0;
  matrix e;
  e.a[0][0] = e.a[1][1] = 1;
  e.a[0][1] = e.a[1][0] = 0;
  while (x > 0) {
    if (x % 2) e = e * b;
    b = b * b;
    x /= 2;
  }
  return e.a[0][1];
}
vector<long long> d;
int main() {
  ios_base::sync_with_stdio(0);
  cin >> m >> l >> r >> k;
  for (int x = 1; x <= (int)2e6; x++) d.push_back(x);
  for (int x = 1; x <= (int)2e6; x++) {
    long long fl = l / x;
    d.push_back(fl + 1);
    if (fl > 0) {
      d.push_back(fl);
    }
    if (fl - 1 > 0) d.push_back(fl - 1);
  }
  for (int x = 1; x <= (int)2e6; x++) {
    long long fl = r / x;
    d.push_back(fl + 1);
    if (fl > 0) {
      d.push_back(fl);
    }
    if (fl - 1 > 0) d.push_back(fl - 1);
  }
  for (long long x : d) {
    if (x > r) continue;
    long long hi = r / x * x;
    long long lo = (l / x + (l % x ? 1 : 0)) * x;
    long long curr = (hi - lo) / x + 1;
    if (curr >= k) {
      res = max(res, x);
    }
  }
  cout << get_fib(res);
  return 0;
}
