#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1, 0};
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
const int inf = 1 << 30;
const long long INF = 1ll << 62;
const double eps = 1e-9;
long long l, r, cur, k, m, mid, mmid, ans;
struct matrix {
  long long a[2][2];
  matrix() { memset(a, 0, sizeof(a)); }
  matrix operator*(matrix b) {
    matrix r;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
          r.a[i][j] = (r.a[i][j] + a[i][k] * b.a[k][j]) % m;
    return r;
  }
};
long long f(long long n) {
  matrix a, e;
  a.a[0][1] = a.a[1][0] = a.a[1][1] = 1;
  e.a[0][0] = e.a[1][1] = 1;
  while (n) {
    if (n & 1) {
      n--;
      e = e * a;
    } else {
      n /= 2;
      a = a * a;
    }
  }
  return e.a[1][0];
}
int main() {
  cin >> m >> l >> r >> k;
  for (mid = 1; mid <= 1000000; mid++) {
    cur = r / mid - (l - 1) / mid;
    if (cur >= k) ans = max(ans, mid);
    mmid = r / mid;
    if (!mmid) continue;
    cur = r / mmid - (l - 1) / mmid;
    if (cur >= k) ans = max(ans, mmid);
  }
  cout << f(ans);
  return 0;
}
