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$$.