26521번 - 연립방정식

문제

$n$개의 서로 다른 양의 정수 $a_1, a_2, \cdots ,a_n$ 이 주어진다.

다음을 만족하는 $n$개의 정수 $x_1, x_2, \cdots ,x_n$ 이 존재한다면 이들을 10ドル^9+7$로 나눈 나머지를 한 줄에 공백으로 구분하여 출력하고, 존재하지 않는다면 NO를 출력하시오.

• 0ドル \leq m \leq n-1$ 인 모든 정수 $m$에 대하여,

$$ \sum_{i=1}^{n} \frac {{a_i}^{m}}{x_i} = \begin{cases} 0 & \text{(0ドル \leq m < n-1$)}\\ 1 & \text{($m=n-1$)}\\ \end{cases} $$

입력

첫 번째 줄에 양의 정수의 개수 $n$이 주어진다. $(2 \leq n \leq 5,000円)$

두 번째 줄에 $a_1,ドル $a_2,ドル $\cdots,ドル $a_n$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 10^9)$

출력

조건을 만족하는 $n$개의 정수 $x_1,ドル $x_2,ドル $\cdots,$ $x_n$ 이 존재한다면 이들을 10ドル^9+7$로 나눈 나머지를 한 줄에 공백으로 구분하여 출력하고, 존재하지 않는다면 NO를 출력한다.

제한

노트

이 조건을 만족하는 $x_1, x_2, ... ,x_n$ 이 존재한다면 유일함을 보일 수 있다. 임의의 정수 $a$와 양의 정수 $b$에 대해서, $a=bq+r(0 \leq r < b)$이 되는 정수 $q$와 $r$이 유일하다. 이때 $r$을 $a$를 $b$로 나눈 나머지로 정의한다.