C. 간단한 확률 문제

문제

바구니 안에 $n$ 개의 공이 있다. 각 공은 $1$ 부터 $c$ 까지의 색 중 하나를 가지고 있다. $i$ 번째 공의 색을 $a_i$ 라 하자.

다음과 같은 시행을 $m$ 회 진행한다.

각 시행에서 바구니 안의 모든 공은 같은 확률로 뽑힌다.

모든 시행이 끝난 후, 바구니에서 공 하나를 무작위로 뽑는다. 앞선 $m$ 번의 시행에서 이루어진 모든 무작위 선택과 마지막 공을 뽑는 무작위 선택을 모두 고려했을 때, 마지막으로 뽑은 공의 색이 $i$ 일 확률을 $p_i$ 라 하자.

모든 $i \in \{1, 2, \dots, c\}$ 에 대해 $p_i$ 를 구하여라.

첫 줄에는 처음 바구니에 들어 있는 공의 수 $n$ , 색의 가짓수 $c$ , 시행의 횟수 $m$ 이 공백으로 구분되어 주어진다.

둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \dots, a_n$ 이 공백으로 구분되어 주어진다. 는 번째 공의 색을 나타낸다.

$p_1, p_2, \dots, p_c$ 를 으로 나눈 나머지를 공백으로 구분하여 출력한다.

#	得点	制約
1	100	-

例 1

入力例

5 3
3 5
2 1000000000

出力例

332748118 0 332748118 0 332748118

첫 번째 예시에서 색 $2$ 와 색 $4$ 인 공은 처음부터 없으므로 이후에도 추가되지 않고, 해당 색상의 확률은 $0$ 이다.

例 2

入力例

4 2 1
1 2 1 1
1

出力例

249561089 748683265

두 번째 예시의 첫 시행에서는 뽑은 공을 제거한 뒤 같은 색의 공 하나를 넣으므로, 어떤 공이 뽑히더라도 색별 공의 개수는 변하지 않는다. 따라서 마지막에 색 $1$ 과 색 $2$ 가 뽑힐 확률은 각각 과 이다.