수식 알아맞히기 퀴즈 게임

시간 제한3초메모리 제한1024 MB

요약

소수 p에서 f(1)부터 f(p-1)까지의 나머지가 주어질 때, f(x) = 합 a_i * i^x (mod p)를 만족하는 계수 a_1부터 a_(p-1)을 구합니다.

문제

정수론 시험을 망친 시루와 루시는 정수론을 배우려고 깊은 산속에 사는 정수론 도사 ahgus를 찾아갔다. ahgus는 퀴즈 게임으로 제자를 받기로 했다.

그에게는 사랑하는 소수 $p$ 와 다음과 같은 함수가 있다.

$f(x) = \sum\_{i=1}^{p-1} a\_{i}i^{x} \, (0 \leq a\_{i} \leq p-1)$

그는 둘에게 함숫값 $f(1)$ , $f(2)$ , $\cdots$ , $f(p-1)$ 을 각각 $p$ 로 나눈 나머지를 알려주었다. 그리고 사랑하는 함수를 알아맞히는 사람만이 제자가 될 자격이 있다고 말했다.

시루와 루시를 도와 함수를 계산해 주자.

첫째 줄에 소수 $p$ 가 주어진다. 둘째 줄에는 $f(1)$ , $f(2)$ , $\cdots$ , $f(p-1)$ 을 각각 $p$ 로 나눈 나머지가 공백으로 구분되어 주어진다.

$a\_1$ , $a\_2$ , ..., $a\_{p-1}$ 을 출력한다. 모든 $a\_i$ 는 항상 유일하게 존재하며 정수임을 증명할 수 있다.

$p \leq 300,000$