Description

Combinatorics is an important branch of mathematics that studies discrete objects. It mainly focuses on problems about the existence, counting, and construction of configurations (also called combinatorial models) that satisfy certain conditions. Its main topics include combinatorial counting, combinatorial design, combinatorial matrices, and combinatorial optimization.

With the rapid development of computer science, the importance of combinatorics has become more and more evident, because the core of computer science is using algorithms to process discrete data.

Today we study an interesting and simple counting problem in combinatorics:

From a deck of $n$ distinct playing cards, deal to $m$ people; the $i$-th person receives $a_i$ cards. Find the number of ways to do this. This number may be very large; please output the result modulo $10007$.

Input Format

The first line contains two integers $n, m$.

The second line contains $m$ integers $a_i$.

Output Format

Output the result modulo $10007$.

5 2
3 1

20

20 19
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

8707

Hint

For $50\%$ of the testdata: $a_i = 1$.

For $100\%$ of the testdata: $1 \leq n \leq 10^4$, $1 \leq m \leq 100$, $0 \leq a_i \leq 100$.

Translated by ChatGPT 5