#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e6 + 5;
long long d[MAXN];
int top = 0;
long long t[3][3], a[3][3], res[3][3];
void binpow(long long st, long long MOD) {
  res[1][1] = res[2][2] = 1;
  for (; st; st >>= 1) {
    if (st & 1) {
      for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
          t[i][j] = 0;
          for (int k = 1; k <= 2; k++) {
            long long cur = (res[i][k] * a[k][j]) % MOD;
            t[i][j] = (t[i][j] + cur) % MOD;
          }
        }
      }
      for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++) {
          res[i][j] = t[i][j];
        }
      }
    }
    for (int i = 1; i <= 2; i++) {
      for (int j = 1; j <= 2; j++) {
        t[i][j] = 0;
        for (int k = 1; k <= 2; k++) {
          long long cur = (a[i][k] * a[k][j]) % MOD;
          t[i][j] = (t[i][j] + cur) % MOD;
        }
      }
    }
    for (int i = 1; i <= 2; i++) {
      for (int j = 1; j <= 2; j++) {
        a[i][j] = t[i][j];
      }
    }
  }
}
void solve() {
  long long m, r, l, k;
  cin >> m >> l >> r >> k;
  if (m == 1) {
    cout << 0;
    return;
  }
  for (long long i = 1; i * i <= l; i++) {
    d[top++] = i;
    if (i > 1) {
      d[top++] = i - 1;
    }
  }
  for (long long i = 1; i * i <= r; i++) {
    d[top++] = i;
    d[top++] = r / i;
  }
  long long ans = -1;
  for (int i = 0; i < top; i++) {
    long long cnt = (r / d[i]) - 1ll * ceil(1. * l / d[i]) + 1;
    if (cnt >= k) {
      ans = max(ans, d[i]);
    }
  }
  cerr << ans << endl;
  a[1][1] = a[1][2] = a[2][1] = 1;
  if (ans == 1 || ans == 2) {
    cout << 1;
    return;
  }
  binpow(ans - 1, m);
  cerr << res[1][1] << " " << res[1][2] << "\n"
       << res[2][1] << " " << res[2][2];
  cout << (res[2][1] + res[2][2]) % m;
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
