27731번 - 경우의 수

문제

토끼 나라에는 1ドル$번부터 $N$번까지 $N$마리의 토끼가 있다. 토끼는 정수를 좋아한다. $i$번 토끼가 가장 좋아하는 정수는 $r_i$이다. 토끼는 자신이 가장 좋아하는 정수를 공개하지 않는다. 서로 다른 두 토끼가 가장 좋아하는 정수가 같을 수도 있다.

토끼 나라에 잠입한 곰은 토끼가 집합 $X=\{x_1,x_2,\cdots ,x_M\}$에 포함된 정수만 좋아한다는 사실을 알아냈다. 모든 $i$에 대해 $i$번 토끼가 가장 좋아하는 정수 $r_i$는 집합 $X$에 포함된 $M$개의 정수 중 하나이다.

토끼 나라의 잠재력은 $\prod_{i=1}^{N}{r_i}$이다. 곰은 1ドル\le k\le K$인 정수 $k$에 대해 토끼 나라의 잠재력이 $k$인 경우가 몇 가지인지 세어보려고 한다. 어떤 $i$에 대해 $i$번 토끼가 가장 좋아하는 정수 $r_i$가 다르다면 서로 다른 경우이다.

토끼 나라의 잠재력이 $k$인 경우의 수를 $f(k)$라고 할 때 $f(1) ,f(2) ,\cdots ,f(K)$를 구하시오.

입력

첫 번째 줄에 $N,M,K$가 공백으로 구분되어 주어진다. $(1\le N\le 10^9;$ 1ドル\le M,K\le 2\times 10^5)$

두 번째 줄에 $x_1,x_2,\cdots ,x_M$이 공백으로 구분되어 주어진다. $(1\le x_i\le 10^9;$ $x_i<x_{i+1})$

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 $f(1) ,f(2) ,\cdots ,f(K)\pmod{1,円 000,円 000,円 007}$을 공백으로 구분하여 출력한다.

제한

힌트