#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  long long t[2][2];
  long long* operator[](int x) { return t[x]; }
  long long const* operator[](int x) const { return t[x]; }
  Matrix() { memset(t, 0, sizeof(t)); }
};
long long m;
Matrix operator*(const Matrix& a, const Matrix& b) {
  Matrix result;
  for (int i = 0; i < 2; ++i) {
    for (int k = 0; k < 2; ++k) {
      for (int j = 0; j < 2; ++j) {
        result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % m;
      }
    }
  }
  return result;
}
int main() {
  long long l, r, k;
  cin >> m >> l >> r >> k;
  long long len = r - l + 1;
  long long x = 1;
  for (long long i = 1; i <= 1000000; ++i) {
    if (r / i - (l - 1) / i >= k) {
      x = max(x, i);
    }
  }
  for (long long c = 1; c <= 1000000 && c <= r; ++c) {
    long long y = r / c;
    if (r / y - (l - 1) / y >= k) {
      x = max(x, y);
    }
  }
  Matrix a;
  a[0][0] = a[1][0] = a[0][1] = 1 % m;
  Matrix res;
  res[0][0] = res[1][1] = 1 % m;
  for (; x > 0; x >>= 1) {
    if (x & 1) {
      res = res * a;
    }
    a = a * a;
  }
  cout << res[1][0] << endl;
}
