#include <bits/stdc++.h>
using namespace std;
int MOD = 1e8 + 5;
const int maxn = 2;
struct JZ {
  long long m[maxn][maxn];
};
JZ muti(JZ a, JZ b, int mod);
JZ quick_mod(JZ a, long long k, int mod);
bool chk(long long u, long long L, long long R, long long K) {
  if (u == 0) {
    return 0;
  }
  return (R / u) - ((L - 1) / u) >= K;
}
int main() {
  long long L, R, K;
  cin >> MOD >> L >> R >> K;
  long long te = 0;
  for (long long i = 1; i * i <= R; i++) {
    if (chk(i, L, R, K)) {
      te = max(te, i);
    }
  }
  for (long long bs = 1; bs * bs <= R; bs++) {
    if (chk(R / bs, L, R, K)) {
      te = max(te, R / bs);
    }
  }
  for (long long bs = 1; bs * bs <= L - 1; bs++) {
    if ((chk(((L - 1) / bs) - 1, L, R, K))) {
      te = max(te, ((L - 1) / bs) - 1);
    }
  }
  JZ demo, ans;
  demo.m[0][0] = 0;
  demo.m[0][1] = 1;
  demo.m[1][0] = 1;
  demo.m[1][1] = 1;
  ans = quick_mod(demo, te, MOD);
  cout << ans.m[1][0] << endl;
}
JZ muti(JZ a, JZ b, int mod) {
  JZ temp;
  memset(temp.m, 0, sizeof(temp.m));
  for (int i = 0; i < maxn; i++)
    for (int j = 0; j < maxn; j++) {
      for (int k = 0; k < maxn; k++) {
        temp.m[i][j] += (long long)a.m[i][k] * b.m[k][j] % mod;
      }
      temp.m[i][j] %= mod;
    }
  return temp;
}
JZ quick_mod(JZ a, long long k, int mod) {
  JZ ans;
  for (int i = 0; i < maxn; i++)
    for (int j = 0; j < maxn; j++) ans.m[i][j] = (i == j);
  while (k) {
    if (k & 1) ans = muti(ans, a, mod);
    a = muti(a, a, mod);
    k >>= 1;
  }
  return ans;
}
