#include <bits/stdc++.h>
namespace chtholly {
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f ^= c == '-';
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return f ? x : -x;
}
template <typename mitsuha>
inline bool read(mitsuha &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c) && ~c; c = getchar()) f ^= c == '-';
  if (!~c) return 0;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return x = f ? x : -x, 1;
}
template <typename mitsuha>
inline int write(mitsuha x) {
  if (!x) return 0 & putchar(48);
  if (x < 0) x = -x, putchar('-');
  int bit[20], i, p = 0;
  for (; x; x /= 10) bit[++p] = x % 10;
  for (i = p; i; --i) putchar(bit[i] + 48);
  return 0;
}
inline char fuhao() {
  char c = getchar();
  for (; isspace(c); c = getchar())
    ;
  return c;
}
}  // namespace chtholly
using namespace chtholly;
using namespace std;
const int mod = read();
long long l, r, k;
bool judge(long long x) {
  long long ans = r / x - l / x;
  if (l % x == 0) ans++;
  return ans >= k;
}
struct juzhen {
  long long m[3][3];
  void clearit() {
    memset(m, 0, sizeof m);
    m[1][1] = m[2][2] = 1;
  }
  void clear() { memset(m, 0, sizeof m); }
  juzhen operator*(const juzhen &b) const {
    int i, j, k;
    juzhen ans;
    ans.clear();
    for (i = 1; i < 3; ++i) {
      for (j = 1; j < 3; ++j) {
        for (k = 1; k < 3; ++k) {
          ans.m[i][j] = (ans.m[i][j] + m[i][k] * b.m[k][j]) % mod;
        }
      }
    }
    return ans;
  }
};
juzhen operator^(juzhen a, long long b) {
  juzhen c;
  c.clearit();
  for (; b; b >>= 1, a = a * a)
    if (b & 1) c = c * a;
  return c;
}
int main() {
  read(l), read(r), read(k);
  long long ans = 0;
  for (long long i = 1; i * i <= r; ++i) {
    if (judge(i)) ans = max(ans, i);
    if (judge(r / i)) ans = max(ans, r / i);
  }
  juzhen tmp;
  tmp.clear();
  tmp.m[1][1] = tmp.m[1][2] = tmp.m[2][1] = 1;
  tmp = tmp ^ ans - 1;
  write((tmp.m[1][1] + mod) % mod);
}
