OI题库

【题目描述】

二项式展开系数大家已经十分熟悉了：

$$ (x+y)^n = \sum^n_{i=0}{\rm C}_n^i x^iy^{n-1} $$

现在我们将问题推广到任意t个实数的和的n次方 $(x_1+x_2+\cdots +x_t)^n$ 的展开式。我们想知道多项式 $(x_1+x_2+\cdots+x_t)^n$ 中的任意一项 $x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}$ 的系数。例如，将一个三项式 $(x_1+x_2+x_3)^3$ 展开后，可以得到：

\[\begin{array}{ll} (x_1+x_2+x_3)^3 & = x_1^3+x_2^3+x_3^3 \\ & + 3x_1^2x_2+3x_1^2x_3 \\ & + 3x_1x_2^2+3x_1x_3^2 \\ & + 3x_2^2x_3+3x_2x_3^2 \\ & + 6x_1x_2x_3 \end{array} \]

其中， $x_1^2x_2$ 的系数为3

【输入格式】

第一行，两个整数n和t，中间用空格分隔。分别表示多项式幂和项数。

第二行，t个整数n1, n2, …， nt，中间用空格分隔。分别表示x1, x2, …, xn的幂。（n1+n2+…+nt=n，1≤n, t≤12）

【输出格式】

仅一行，一个整数（保证在长整型范围内）。表示多项式(x1+x2+…+xt)n中的项的系数。

【样例输入】

3 3
2 1 0

【样例输出】

3