void quickadd(int &res, int val) { if ((res += val) >= MOD) res -= MOD; }
void quicksub(int &res, int val) { if ((res -= val) < 0 ) res += MOD; }
/// Return the value in [0..MOD)
int fix(ll x) { x %= MOD; if (x < 0) x += MOD; return x; }
/// f1(n) = sigma(i=1..n) (1) = n
/// f2(n) = sigma(i=1..n) (i) = n * (n + 1) / 2
/// f3(n) = sigma(i=1..n) f2(i) = n * (n + 1) * (n + 2) / 6
/// sqf1(n) = sigma(i=1..n) i^2 = n * (n + 1) * (2n + 1) / 6 = f2(n) * (2n + 1) / 3
int f1(ll n) { return n % MOD; }
int f2(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * inverse_2 % MOD; }
int f3(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * f1(n + 2 * 1) % MOD * inverse_6 % MOD; }
int sqf1(ll n) { return 1LL * f1(n) * f1(n + 1) % MOD * f1(n * 2 + 1) % MOD * inverse_6 % MOD; }
/// f1(l, r) = sigma(i=l..r) (1)
/// f2(l, r) = sigma(i=l..r) (i)
/// f3(l, r) = sigma(i=l..r) f2(i)
/// sqf1(l, r) = sigma(i=l..r) i^2
int f1(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f1(r) - f1(l - 1)); }
int f2(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f2(r) - f2(l - 1)); }
int f3(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(f3(r) - f3(l - 1)); }
int sqf1(ll l, ll r) { return (l < 0 || l > r) ? 0 : fix(sqf1(r) - sqf1(l - 1)); }
/// sigma(i=l..r) min(i, y)
int g2(ll l, ll r, ll y)
{
minimize(y, r); ll t = max(l, y);
return (f2(l, y - 1) + y * f1(t, r)) % MOD;
}
/// sigma(i=l..r) i * min(i, y)
int g3(ll l, ll r, ll y)
{
minimize(y, r); ll t = max(l, y);
return (sqf1(l, t - 1) + y * f2(t, r)) % MOD;
}
/// sigma(i=l..r) min(k - i, y)
/// = sigma(i=k-r..k-l) min(i, y)
int g2(ll l, ll r, ll y, ll k) { return g2(k - r, k - l, y); }
/// sigma(i=l..r) i * min(k - i, y)
/// = sigma(i=k-r..k-l) * min(y, i) * k + sigma(i=k-r..k-l) min(y, i) * k
int g3(ll l, ll r, ll y, ll k) { return g2(k - r, k - l, y) * k - g3(k - r, k - l, y); }
/// If (x < k) then there is no way to share candies
/// Else there are exact (k - x + 1) ways to share
int solve1(ll x, ll k)
{
return max(0LL, k - x + 1) % MOD;
}
/// max(A.get) = x
/// max(B.get) = y
/// max(A.get + B.get) = k
/// * Take max(x) = min(x, k)
/// * Take min(x) = max(0, k - y) = k - min(y, k)
int solve2(ll x, ll y, ll k)
{
return solve1(k - min(y, k), min(x, k));
}
/// * max(a, b) = a + b - min(a, b)
/// * L = Take min(x) = k - min(k, x)
/// * R = Take max(x) = min(k, y + z)
/// -------------------------------------------------------
/// * Sigma(x = L..R) { solve2(y, z, x) }
/// = Sigma(x = L..R) { f1(max(0, x - y), min(z, x)) }
/// = Sigma(x = L..R) { f1(x - min(x, y), min(z, x)) }
/// = Sigma(x = L..R) { (1 - x + min(x, y) + min(x, z)) }
/// = f1(L, R) - f2(L, R) + g2(L,R, y) + g2(L, R, z)
/// -------------------------------------------------------
/// > f1(L, R) = Sigma(x = L..R) (1)
/// > f2(L, R) = Sigma(x = L..R) (x)
/// > g2(L, R, y) = Sigma(x = L..R) min(x, y)
/// > g2(L, R, z) = Sigma(x = L..R) min(x, z)
int solve3(ll x, ll y, ll z, ll k)
{
ll L = k - min(k, x);
ll R = min(k, y + z);
if (L > R) return 0;
return fix(f1(L, R) - f2(L, R) + g2(L, R, y) + g2(L, R, z));
}
/// * max(x, y, z, t, z + t) <= R
/// * L = Take min(x + y) = k - min(k, z + t)
/// * R = Take max(x + y) = min(k, x + y)
/// -------------------------------------------------------
/// * Sigma(s = L..R) { solve2(x, y, s) * solve2(z, t, k-s) }
///
/// = Sigma(s = L..R) { min(x, s) - s + min(y, s) + 1 }
/// * { min(t, k-s) - k + s + min(z, k-s) + 1 }
///
/// = Sigma(s = L..R) { min(x, s) * min(t, k-s) - s * min(t, k-s) + min(y, s) * min(t, k-s) + min(t, k-s) }
/// + { min(x, s) * min(z, k-s) - s * min(z, k-s) + min(y, s) * min(z, k-s) + min(z, k-s) }
/// - { min(x, s) * k - s * k + min(y, s) * k + k }
/// + { min(x, s) * s - s * s + min(y, s) * s + s }
/// + { min(x, s) - s + min(y, s) + 1 }
///
/// = Sigma(s = L..R) A(k) + B(x) + B(y) + C(k) + D(z, x) + D(z, y) + D(t, x) + D(t, y)
///
/// With X = max(x, L)
/// A(k)> Sigma(s = L..R) { 1 - k + s * k-s * s }
/// = Sigma(s = L..R) (1 - k) + Sigma(s = L..R) (s * k) - Sigma(s = L..R) (s * s)
/// = f1(L, R) * (1 - k) + f2(L, R) * k - sqf1(L, R)
///
/// B(x)> Sigma(s = L..R) { min(x, s) * (s - k + 1) }
/// = (1 - k) * Sigma(s = L..X-1) min(x, s) + Sigma(s = L..X-1) min(x, s) * s
/// = (1 - k) * (f2(L, X-1) + f1(X, R) * x) + sqf1(L, X - 1) + f2(X, R) * x
///
/// C(k)> Sigma(s = L..R) { min(z, k-s) * (1 - s) }
/// = Sigma(s = L..R) min(z, k-s) - Sigma(s = L..R) min(z, k-s) * s
/// = g2(L, R, z, k) - g3(L, R, z, t)
///
/// D(z, x)> Sigma(s = L..R) { min(z, k-s) * min(x, s) }
/// = Sigma(s = L..X-1) min(z, k-s) * s + Sigma(s = X..R) min(z, k-s) * x
/// = g3(L, X - 1, z, k) + g2(X, R, z, k) * x
/// ---------------------------------------------------------------------------------------------------------------------------------
int solve4(ll x, ll y, ll z, ll t, ll k)
{
ll L = k - min(k, z + t);
ll R = min(k, x + y);
if (L > R) return 0;
minimize(x, R);
minimize(y, R);
ll X = max(L, x), Y = max(L, y);
int res = 0;
quickadd(res, fix(0LL + f1(L, R) * (1 - k) + f2(L, R) * k - sqf1(L, R))); /// A(k)
quickadd(res, fix(0LL + (1 - k) * (f2(L, X - 1) + f1(X, R) * x) + sqf1(L, X - 1) + f2(X, R) * x)); /// B(x)
quickadd(res, fix(0LL + (1 - k) * (f2(L, Y - 1) + f1(Y, R) * y) + sqf1(L, Y - 1) + f2(Y, R) * y)); /// B(y)
quickadd(res, fix(0LL + g2(L, R, z, k) - g3(L, R, z, k))); /// C(z)
quickadd(res, fix(0LL + g2(L, R, t, k) - g3(L, R, t, k))); /// C(z)
quickadd(res, fix(0LL + g3(L, X - 1, z, k) + g2(X, R, z, k) * x)); /// D(x, z)
quickadd(res, fix(0LL + g3(L, Y - 1, z, k) + g2(Y, R, z, k) * y)); /// D(y, z)
quickadd(res, fix(0LL + g3(L, X - 1, t, k) + g2(X, R, t, k) * x)); /// D(x, t)
quickadd(res, fix(0LL + g3(L, Y - 1, t, k) + g2(Y, R, t, k) * y)); /// D(y, t)
return res;
}