Let's define the score of sequence $A$ of length $M$ the maximal number $T$ such that there exist a sequence $B$  of length $T$ with $1 = B_1 < B_2 < \dots < B_T \le M$ and $B_i$ is the smallest index bigger than $B_{i - 1}$ with $A_{B_{i - 1}} \le A_{B_{i}}$.

A sequence $S$ of length $N$ is randomly generated in the following way:

$\cdot$ For each index $i$ we assign $V$ $(1 \le V \le K)$ to $S_i$ with probability $p_V$.

Find the expected score of $S$ modulo $10^9 + 7$.

$\textbf{Input}$

The first line contains two integers - $N, K (1 \le N \le 10^9, 1 \le K \le 75)$.

The next line contains $K$ nonegative integers - $q_1, q_2, \dots, q_k$, $p_i = \frac{q_i}{q_1 + q_2 + \dots + q_k}$ $(1 \le q_1 + q_2 + \dots + q_k \le 10^9)$.

$\textbf{Output}$

It can be proved that the answer can be represented as a fraction $\frac{P}{Q}$ with $Q \neq 0$ and $(P,Q) = 1$. Output the reminder of $P \cdot Q ^ {-1}$ when divided by $10^9 + 7$.