#include <cstdio>
#include <algorithm>

using namespace std;

int mod, G;

typedef long long ll;
typedef __uint128_t L;
struct FastMod {
  ll b, m;
  FastMod(ll b): b(b), m(ll((L(1) << 64) / b)) {}
  ll operator()(ll a) {
    ll q = (ll)((L(m) * a) >> 64);
    ll r = a - q * b; // can be proven that 0 <= r < 2*b
    return r >= b ? r - b : r;
  }
} R(2);
inline int norm(int x) {
  return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
  return x < 0 ? x + mod : x;
}
inline int mpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1) {
    if (b & 1)
      ret = R((ll)ret * a);
    a = R((ll)a * a);
  }
  return ret;
}

const int M = 1e6;
ll n, st, ed, k;
int r;
int GPow[M], GLog[M], inv[M];
int fac[M], ifac[M];
int a[M];

inline int getG() {
  int p[20], cnt = 0;
  int t = mod - 1;
  for (int i = 2; i * i <= t; ++i) {
    if (t % i == 0)
      p[cnt++] = i;
    while (t % i == 0)
      t /= i;
  }
  if (t > 1)
    p[cnt++] = t;
  for (int G = 2; ; ++G) {
    bool flag = 1;
    for (int i = 0; i < cnt; ++i)
      if (mpow(G, (mod - 1) / p[i]) == 1) {
        flag = 0;
        break;
      }
    if (flag)
      return G;
  }
}

int binom(ll n, ll m) {
  if (n < m || m < 0)
    return 0;
  if (n < mod)
    return R(R((ll)fac[n] * ifac[m]) * ifac[n - m]);
  return R((ll)binom(n / mod, m / mod) * binom(n % mod, m % mod));
}

int calc(ll m, ll n) {
  if (m < 0)
    return 0;
  m = min(n, m);
  if (n < mod) {
    int ret = R((ll)a[0] * (m + 1));
    for (int k = 1, t = 0; k < mod - 1; ++k)
      t = t >= m + 1 ? t - m - 1 : t - m - 1 + mod - 1,
      ret = R(R((ll)(GPow[t] - 1) * inv[GPow[mod - 1 - k] - 1]) * a[k] + ret);
    ret = reduce(-ret);
    return ret;
  }
  m -= k;
  if (m < 0)
    return 0;
  ll a = m / (mod - 1);
  int b = m % (mod - 1);
  int tmp = binom(k - 1, a);
  if ((k - a - 1) & 1)
    tmp = reduce(-tmp);
  int ret = R((ll)tmp * (calc(b - mod + 1, r) - calc(b, r) + mod));
  if (b < r && a > 0) {
    tmp = binom(k - 1, a - 1);
    if ((k - a) & 1)
      tmp = reduce(-tmp);
    ret = R((ll)tmp * (calc(b, r) - calc(b + mod - 1, r) + mod) + ret);
  }
  return ret;
}

int main() {
  scanf("%lld%lld%lld%d", &n, &st, &ed, &mod);
  R = FastMod(mod), G = getG();
  GPow[0] = 1;
  for (int i = 1; i < mod - 1; ++i)
    GLog[GPow[i] = R((ll)GPow[i - 1] * G)] = i;
  inv[1] = 1;
  for (int i = 2; i < mod - 1; ++i)
    inv[i] = GPow[mod - 1 - GLog[i]];
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= mod - 1; ++i)
    fac[i] = R((ll)fac[i - 1] * i),
    ifac[i] = R((ll)ifac[i - 1] * inv[i]);
  k = n / mod, r = n % mod;
  for (int k = 0; k < mod - 1; ++k) {
    int x = GPow[k];
    if (x < mod - r + 1)
      a[k] = R((ll)fac[x + r - 1] * ifac[x - 1]);
  }
  printf("%d\n", reduce(calc(ed, n) - calc(st - 1, n)));
}