Distribution of Cards

In combinatorial mathematics, one classic problem is to count the number of ways to distribute a set of distinct items among several people under given constraints. In this problem, you are given a deck of n distinct cards and m persons. The i-th person must receive exactly a_i cards. You are required to count the total number of distributions possible. The answer can be expressed by the multinomial coefficient

[ \binom{n}{a_1, a_2, \dots, a_m} = \frac{n!}{a_1!,a_2!,\cdots,a_m!}, ]

Since the result can be extremely large, output the final answer modulo 10007.

Note: It is guaranteed that \(a_1 + a_2 + \cdots + a_m = n\).

inputFormat

The first line contains two integers n and m representing the number of cards and the number of persons respectively. The second line contains m space separated integers: a₁, a₂, ..., a_m, where \(a_1 + a_2 + \cdots + a_m = n\).

outputFormat

Output a single integer, the number of ways to distribute the n cards modulo 10007.

sample

5 2
2 3

10