#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
int dblcmp(double d) {
  if (fabs(d) < eps) return 0;
  return d > eps ? 1 : -1;
}
long long mod;
long long l, r, d;
const int maxn = 10;
int n;
struct Mat {
  long long mat[maxn][maxn];
} A, ans, E, M;
Mat operator*(Mat a, Mat b) {
  Mat c;
  memset(c.mat, 0, sizeof(c.mat));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
        c.mat[i][j] %= mod;
      }
    }
  }
  return c;
}
Mat operator+(Mat a, Mat b) {
  Mat c;
  memset(c.mat, 0, sizeof(Mat));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) c.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % mod;
  return c;
}
Mat operator^(Mat A, long long x) {
  Mat c = E;
  for (; x; x >>= 1) {
    if (x & 1) c = c * A;
    A = A * A;
  }
  return c;
}
int main() {
  int i, j, k;
  n = 2;
  for (i = 0; i < n; i++) {
    E.mat[i][i] = 1;
  }
  cin >> mod >> l >> r >> d;
  long long t = 1, ans = 1;
  vector<long long> v;
  for (t = 1; t * t <= l * 2; t++) {
    v.push_back((l + t - 1) / t);
    v.push_back(t);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (__typeof(v.begin()) e = v.begin(); e != v.end(); ++e) {
    long long t = *e;
    long long low = (l + t - 1) / t;
    long long high = r / (t + d - 1);
    if (low <= high) {
      ans = max(ans, high);
    }
  }
  A.mat[0][0] = A.mat[0][1] = A.mat[1][0] = 1;
  M = (A ^ (ans - 1));
  cout << M.mat[0][0] % mod << endl;
  return 0;
}
