1405. Deal the Whole Pile Into Named Groups

There are k labelled groups, and group i must receive exactly a[i] items. The items are all distinguishable, and there are s = a[0] + ... + a[k-1] of them in total, exactly enough. Print the number of ways to deal them out, modulo a prime p.

k = 3, p = 1000000007, a = 1 1 1 -> 6

Three distinct items into three groups of one each is 3! = 6 arrangements.

k = 5, p = 1000003, a = 2 3 4 5 6 -> the multinomial of 20 items

A group may be required to receive 0 items, in which case there is exactly one way to satisfy it.

## What most people try first

Multiply binomials one group at a time: choose a[0] of the s items, then a[1] of what is left, and so on. That is correct, and it is the right idea, but implemented naively it computes k separate modular inverses and rebuilds factorials for each shrinking total. The cost is O(k * s) with a modular power per group.

## One formula, one table

Telescoping that product collapses the intermediate factorials entirely:

C(s, a0) * C(s-a0, a1) * C(s-a0-a1, a2) * ... s! (s-a0)! (s-a0-a1)! s! = -------- * -------------- * ---------------- * ... = ------------------ a0!(s-a0)! a1!(s-a0-a1)! a2!(...)! a0! a1! ... a[k-1]!

Every numerator after the first cancels against the denominator before it. So build f[i] = i! mod p and g[i] = inv(i!) mod p once, up to s, with a single modular power as in problem 1401, and the answer is one product of k + 1 table entries:

answer = f[s] * g[a0] * g[a1] * ... * g[a[k-1]] mod p

## Why it is correct

The multinomial coefficient counts the ways to partition a set of s distinguishable items into labelled blocks of the prescribed sizes. Line up all s items in one of s! orders and hand the first a[0] to group 0, the next a[1] to group 1, and so on. Every deal arises this way, and each deal arises from exactly a[0]! * a[1]! * ... * a[k-1]! of the orderings, since permuting items within a group does not change who got what. Dividing gives the formula.

The inverses exist because p is prime and s < p, so no factorial up to s contains the factor p. That is the same guarantee problem 1401 relies on, and it is why the constraint pins p above 10^6 while s stays at or below 10^6.

A group with a[i] = 0 contributes g[0] = 1, so the formula needs no special case for it.

## The boundary that breaks a careless implementation

s can be 0, when every group wants nothing. The answer is then 1, the empty deal, and a table built to size 0 must still contain f[0] = g[0] = 1. The references build to max(s, 1) so that the downward inverse recurrence has somewhere to start.

## Overflow

p reaches 1000000009, so each of f[i-1] * i, f[s] * g[a0] and every subsequent step is a product of two values near 10^9, which is near 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and does not fit a signed 32-bit one, whose limit is 2147483647: a 32-bit build answers 948719427 where the truth is 412083817. The sum s itself is at most 10^6 and fits anywhere. In JavaScript the products pass 2^53, so the references split one factor at 65536, which keeps every intermediate exact without two million BigInt allocations.

## Cost

O(s + log p).

Constraints - `1 ≤ k ≤ 10` - `0 ≤ a[i] ≤ 1000000` - `a[0] + ... + a[k-1] ≤ 1000000` - `1000003 ≤ p ≤ 1000000009` and `p` is prime