Gift Distribution

Little E purchased n distinct gifts from a store and intends to distribute them among m people. The i^th person should receive exactly \(w_i\) gifts. Two schemes are considered different if and only if there exists at least one person who receives a different set of gifts between the two schemes.

If \(\sum_{i=1}^{m}w_i \neq n\), then the answer is 0. Otherwise, the number of ways to distribute the gifts is given by:

\[ \frac{n!}{w_1!w_2!\cdots w_m!} \]

Since the result can be very large, output the answer modulo \(P\).

inputFormat

The first line of input contains three integers n, m and P separated by spaces.

The second line contains m integers \(w_1, w_2, \ldots, w_m\) separated by spaces.

outputFormat

Output a single integer: the number of ways to distribute the gifts modulo P.

sample

5 2 1000000007
2 3

10