A false witness that speaketh lies!

You are given a sequence containing $*n*$ integers. There is a variable $*res*$ that is equal to $0$ initially. The following process repeats $*k*$ times.

Choose an index from $1$ to $*n*$ uniformly at random. Name it $*x*$. Add to $*res*$ the multiply of all $*a*_{*i*}$'s such that $1 ≤ *i* ≤ *n*$, but $*i* ≠ *x*$. Then, subtract $*a*_{*x*}$ by $1$.

You have to find expected value of $*res*$ at the end of the process. It can be proved that the expected value of $*res*$ can be represented as an irreducible fraction . You have to find .

Input

The first line contains two integers $*n*$ and $*k*$ ($1 ≤ *n* ≤ 5000$, $1 ≤ *k* ≤ 10^{9}$) — the number of elements and parameter $*k*$ that is specified in the statement.

The second line contains $*n*$ space separated integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($0 ≤ *a*_{*i*} ≤ 10^{9}$).

Output

Output a single integer — the value .