Lencycles

Cerință

Se dau $n$, $k$ și apoi $k$ numere naturale. Se cunoaște că suma acestor $k$ numere este $n$. Să se determine câte permutări de lungime $n$ există cu proprietatea că acestea au exact $k$ cicli, iar lungimile acestor cicli sunt exact numerele date.
Un ciclu se definește ca un subset al permutării în care elementele schimbǎ locurile unele cu altele. Exemplu: $\{4, 2, 1, 3\}$, permutarea conține $2$ cicli $(4, 1, 3) (1 \rightarrow 4 \rightarrow 3 \rightarrow 1)$ și $(2)$.

Date de intrare

Pe prima linie a fișierului de intrare lencycles.in se găsesc două numere întregi, $n$ și $k$.
Pe a doua linie se află cele $k$ numere reprezentând lungimile ciclilor.

Date de ieșire

Fișierul de ieșire lencycles.out va conține un singur număr întreg reprezentând numărul de permutări cerut, modulo $10^9+7$.

Restricții și precizări

• Pentru teste in valoare de 18 de puncte, 1$\leq n \leq 10$;
• Pentru alte teste in valoare de 42 de puncte, 1$\leq n \leq 1000$ și se garantează că lungimile ciclilor vor fi numere distincte;
• Pentru alte teste in valoare de 21 de puncte, 1$\leq n \leq 100 \ 000$ și se garantează că lungimile ciclilor vor fi numere distincte;
• Pentru alte teste in valoare de 19 de puncte, 1$\leq n \leq 100 \ 000$;

Exemplu

lencycles.in

3 2
1 2

lencycles.out

3

Explicație

Avem de determinat câte permutări de lungime $3$ au $2$ cicli, unul de lungime $1$ și unul de lungime $2$.
Sunt în total $6$ permutări de lungime $3$. Dintre acestea, doar permutările $(2, 1, 3)$, $(3, 2, 1)$ și $(1, 3, 2)$ au exact $2$ cicli, unul de lungime $1$ și unul de lungime $2$.