Sequence (Hard)

You are given a sequence $A_1, A_2, \cdots, A_N$ of $N$ positive integers and an integer $M$. A sequence $B_1, B_2, \cdots, B_M$ is called a good sequence if it satisfies all of the following.

• Its length is $M$.
• Every element is an integer between $1$ and $N$.
• It is increasing: $B_1 < B_2 < \cdots < B_M$.
• $A_{B_1}, A_{B_2}, \cdots, A_{B_M}$ are pairwise distinct.

Over all good sequences $B_1, \cdots, B_M$, find the sum of $A_{B_1} \times A_{B_2} \times \cdots \times A_{B_M}$ modulo $1\,000\,000\,007$.

The first line contains the length $N$ of the sequence $A$ and the length $M$ of a good sequence, separated by a space.

The second line contains the sequence $A_1, A_2, \cdots, A_N$, separated by spaces.

Over all good sequences $B_1, \cdots, B_M$, print the sum of $A_{B_1} \times A_{B_2} \times \cdots \times A_{B_M}$ modulo $1\,000\,000\,007$.

• $1 \le N \le 1\,000$
• $1 \le M$
• $1 \le A_i \le 100\,000$ ($1 \le i \le N$)
• $M$ is at most the number of distinct values in $A$.

The sequence $[3, 1, 1, 2]$ in the sample has two good sequences, $[1, 2, 4]$ and $[1, 3, 4]$. The required answer is $3 \times 1 \times 2 + 3 \times 1 \times 2 = 12$.