시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB148696250.000%

문제

모든 원소가 양의 정수이고, 길이가 $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$에 존재하는 서로 다른 수의 개수보다 작거나 같다.

예제 입력 1

4 3
3 1 1 2

예제 출력 1

12

힌트

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

출처

High School > 세종과학예술영재학교 > SASA Programming Contest 2021 C2번