#include <bits/stdc++.h>
using namespace std;
const int max_n = 12;
long long fib[max_n];
long long mat[2][2];
long long ini[2];
long long m;
void mul1(long long a[][2], long long b[][2]) {
  long long c[2][2];
  c[0][0] = a[0][0];
  c[0][1] = a[0][1];
  c[1][0] = a[1][0];
  c[1][1] = a[1][1];
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      a[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        a[i][j] += c[i][k] * b[k][j];
      }
      a[i][j] %= m;
    }
  }
}
void mul2(long long a[][2]) {
  long long c[2][2];
  c[0][0] = a[0][0];
  c[0][1] = a[0][1];
  c[1][0] = a[1][0];
  c[1][1] = a[1][1];
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      a[i][j] = 0;
      for (int k = 0; k < 2; k++) {
        a[i][j] += c[i][k] * c[k][j];
      }
      a[i][j] %= m;
    }
  }
}
int main() {
  fib[1] = fib[2] = 1;
  long long l, r, k;
  cin >> m >> l >> r >> k;
  long long g = 1;
  g = (r - (l - 1)) / k;
  long long maxg = g;
  for (g; g * k <= r - (l - 1) + g + 1 && g <= r;) {
    g = r / (r / g);
    if (g * k <= r - (l - 1) + (l - 1) % g) maxg = g;
    g++;
  }
  mat[0][0] = mat[0][1] = mat[1][0] = 1;
  ini[0] = ini[1] = 1;
  long long n = maxg;
  long long tem[2][2] = {};
  tem[0][0] = tem[1][1] = 1;
  if (n <= 2) {
    cout << fib[n] % m << endl;
  } else {
    n -= 2;
    while (n) {
      if (n % 2 == 1) {
        mul1(tem, mat);
      }
      mul2(mat);
      n /= 2;
    }
    long long ret = tem[0][0] + tem[0][1];
    ret %= m;
    cout << ret << endl;
  }
  return 0;
}
