#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet {
long long mod;
class Matrix {
 private:
  long long a[5][5];

 public:
  long long n;
  Matrix() {
    memset(a, 0, sizeof(a));
    n = 0;
  }
  Matrix(long long _n) {
    memset(a, 0, sizeof(a));
    n = _n;
  }
  Matrix(long long _n, long long _x) {
    _x %= mod;
    n = _n;
    for (long long i = 0; i < 5; ++i) {
      for (long long j = 0; j < 5; ++j) {
        a[i][j] = _x;
      }
    }
  }
  long long* operator[](long long i) { return *(a + i); }
  void Set(long long x) {
    x %= mod;
    for (long long i = 0; i < 5; ++i) {
      for (long long j = 0; j < 5; ++j) {
        a[i][j] = x;
      }
    }
  }
  void Identity() {
    memset(a, 0, sizeof(a));
    for (long long i = 0; i < 5; ++i) {
      a[i][i] = 1;
    }
  }
};
Matrix operator*(Matrix x, Matrix y) {
  Matrix ans(x.n, 0);
  long long n = ans.n;
  for (long long i = 1; i <= n; ++i) {
    for (long long j = 1; j <= n; ++j) {
      for (long long k = 1; k <= n; ++k) {
        ans[i][j] += x[i][k] * y[k][j];
        ans[i][j] %= mod;
      }
    }
  }
  return ans;
}
Matrix operator^(Matrix x, long long p) {
  Matrix ans(x.n, 1);
  ans.Identity();
  while (p) {
    if (p & 1) ans = ans * x;
    x = x * x, p >>= 1;
  }
  return ans;
}
long long Fib(long long x) {
  Matrix Init(2, 0);
  Init[1][1] = 0, Init[1][2] = 1;
  Matrix Trans(2, 1);
  Trans[1][1] = 0;
  Matrix Ans = Init * (Trans ^ x);
  return Ans[1][1];
}
long long l, r, k;
void R1(long long& x) {
  x = 0;
  char c = getchar();
  long long f = 1;
  while (c < '0' or c > '9') f = (c == '-') ? -1 : 1, c = getchar();
  while (c >= '0' and c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  x = (f == 1) ? x : -x;
}
void Input() {
  R1(mod);
  R1(l), R1(r), R1(k);
}
bool cxk(long long x) { return (r / x - (l - 1) / x) >= k; }
void Soviet() {
  long long ans = -0x3f3f3f3f;
  for (long long i = 1; i * i <= r; ++i) {
    if (cxk(i)) ans = max(ans, i);
    if (cxk(r / i)) ans = max(ans, r / i);
  }
  printf("%lld\n", Fib(ans));
}
void IsMyWife() {
  Input();
  Soviet();
}
}  // namespace Flandre_Scarlet
int main() {
  Flandre_Scarlet::IsMyWife();
  getchar();
  getchar();
  return 0;
}
