수열 (Hard)

모든 원소가 양의 정수이고, 길이가 $N$인 수열 $A\_1, A\_2, ..., A\_N$과 $M$이 주어질 때, 우리는 다음 조건을 만족하는 수열 $B\_1, B\_2, \cdots, B\_M$을 좋은 수열이라고 한다.

• 수열의 길이는 $M$이다.
• 모든 원소는 $1$ 이상 $N$ 이하의 정수이다.
• 이 수열은 증가 수열이다. 즉 $B\_1 < B\_2 < \cdots < B\_M$ 이다.
• $A\_{B\_1}, A\_{B\_2}, \cdots, A\_{B\_M}$이 서로 다르다.

가능한 모든 좋은 수열 $B\_1, \cdots, B\_M$에 대해, $A\_{B\_1} \times A\_{B\_2} \times \cdots \times A\_{B\_M}$의 합을 $1\\,000\\,000\\,007$로 나눈 나머지를 구하시오.

첫째 줄에 수열 $A$의 길이 $N$과 좋은 수열의 길이 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 수열 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다.

가능한 모든 좋은 수열 $B\_1, \cdots, B\_M$에 대해, $A\_{B\_1} \times A\_{B\_2} \times \cdots \times A\_{B\_M}$의 합을 $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$은 $A$에 존재하는 서로 다른 수의 개수보다 작거나 같다.

예제에서 주어진 수열 $\[3, 1, 1, 2]$ 에는 두 개의 좋은 수열 $\[1, 2, 4]$와 $\[1, 3, 4]$가 존재한다. 출력해야 하는 답은 $3 \times 1 \times 2 + 3 \times 1 \times 2 = 12$이다.