#include <bits/stdc++.h>
using namespace std;
long long M = 10000;
long long L, R;
long long K;
struct FibMatrix {
  long long f[2][2];
  FibMatrix(long long x, long long y, long long z, long long w) {
    f[0][0] = x;
    f[0][1] = y;
    f[1][0] = z;
    f[1][1] = w;
  }
  FibMatrix operator*(FibMatrix F1) {
    FibMatrix Result(0, 0, 0, 0);
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k)
          Result.f[i][j] =
              (Result.f[i][j] + (this->f[i][k] * F1.f[k][j]) % M) % M;
    return Result;
  }
  FibMatrix operator^(long long t) {
    FibMatrix Answer(1, 0, 0, 1);
    FibMatrix Square = *this;
    while (t) {
      if (t % 2 == 1) Answer = Answer * Square;
      t /= 2;
      Square = Square * Square;
    }
    return Answer;
  }
};
int main() {
  cin >> M >> L >> R >> K;
  long long maxd1 = 1;
  for (long long d = 1; d <= 2000000; ++d) {
    if (R / d - (L - 1) / d >= K) maxd1 = d;
  }
  long long maxd2 = 0;
  if (R / K > L - 1) maxd2 = R / K;
  for (long long l1 = 1; l1 <= 2000000; ++l1) {
    long long d = min(R / (l1 + K), (L - 1) / l1);
    if (d * (l1 + 1) > L - 1) maxd2 = max(maxd2, d);
  }
  long long deg = max(maxd1, maxd2);
  FibMatrix F(1, 1, 1, 0);
  F = F ^ deg;
  cout << F.f[0][1];
  return 0;
}
