Editorial for Difficulties

Approach

If every problem had a distinct label, there would be $n!$ ordered problemsets.

Problems with the same label are indistinguishable, so this overcounts. For each label $i$ the $a_i$ copies can be permuted freely without changing the sequence, so divide by $a_i!$.

The number of distinct sequences is the multinomial coefficient

$\dfrac{n!}{a_1! \, a_2! \, \cdots \, a_k!}$.

Two useful special cases:

• every $a_i = 1$ (so $k = n$): the labels are all distinct and the answer is $n!$;
• one $a_i = n$ and the rest $0$: every problem has the same label (or unused labels contribute $0! = 1$) and the answer is $1$.

Another checkpoint: with two labels the formula is $\binom{n}{a_1} = n! / (a_1! \, a_2!)$.

Precompute factorials and inverse factorials modulo $10^9 + 7$ up to $n$, then multiply $n! \cdot \prod (a_i!)^{-1}$. Time is $O(n)$.

Solution (Python)

MOD = 10**9 + 7
MAXN = 10**6 + 5

fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD
invfact = [1] * MAXN
invfact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = fact[n]
for x in a:
    ans = ans * invfact[x] % MOD
print(ans)