23828번 - 수열 (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$이다.