#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000100;
const int ROZ = 3;
long long m, k, l, r;
struct matrix {
  long long p[ROZ][ROZ];
  int roz;
};
matrix operator*(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i < (a.roz); ++i) {
    for (int j = 0; j < (a.roz); ++j) {
      c.p[i][j] = 0;
    }
  }
  c.roz = a.roz;
  for (int k = 0; k < (a.roz); ++k) {
    for (int i = 0; i < (a.roz); ++i) {
      for (int j = 0; j < (a.roz); ++j) {
        c.p[i][j] = (c.p[i][j] + a.p[i][k] * b.p[k][j]) % m;
        c.p[i][j] = c.p[i][j] % m;
      }
    }
  }
  return c;
}
matrix pot(matrix a, long long n) {
  if (n == 1) {
    return a;
  }
  if (n == 2) {
    return a * a;
  }
  matrix t = pot(a, n / 2);
  if (n % 2 == 0) return t * t;
  return t * t * a;
}
bool sprawdz(long long s, long long r, long long l, long long k) {
  return (s * ((r / s) - (k - 1)) >= l);
}
long long dajWynik() {
  long long t = r / k + 1;
  while (!sprawdz(t, r, l, k)) {
    t = r / (r / t + 1);
  }
  return t;
}
matrix fib;
void readData() {
  cin >> m;
  cin >> l;
  cin >> r;
  cin >> k;
  fib.roz = 2;
  fib.p[0][0] = 0;
  fib.p[0][1] = 1 % m;
  fib.p[1][0] = 1 % m;
  fib.p[1][1] = 1 % m;
  matrix tt = pot(fib, dajWynik());
  cout << tt.p[0][1] << '\n';
}
int main() { readData(); }
