25396번 - ×ばつ+ ×ばつ

문제

칠판에 $N$개의 정수가 적혀 있다. $A_k$와 $B_k$를 다음과 같이 정의하자.

• $A_k$: 칠판에 임의의 두 수를 골라 지우고, 두 수의 곱을 칠판에 쓰는 작업을 $k$번 한다. 이때, 칠판에 적힌 수를 모두 합한 값의 기댓값.
• $B_k$: 칠판에 임의의 두 수를 골라 지우고, 두 수의 합을 칠판에 쓰는 작업을 $k$번 한다. 이때, 칠판에 적힌 수를 모두 곱한 값의 기댓값.

임의로 두 수를 고를 때 모든 쌍이 선택될 확률은 같으며, 모든 시행은 독립이다.

$A_0,\cdots ,A_{N-1}$과 $B_0,\cdots ,B_{N-1}$을 998ドル,円 244,円 353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 구하여라. 998ドル,円 244,円 353$은 소수이다.

입력

첫 번째 줄에 $N$이 주어진다. $(1\le N\le 200,円 000)$

두 번째 줄에 칠판에 적힌 $N$개의 정수가 공백으로 구분되어 주어진다. 각 수는 0ドル$ 이상 998ドル,円 244,円 353$ 미만이다.

출력

첫 번째 줄에 $A_0,\cdots ,A_{N-1}$을 998ドル,円 244,円 353$으로 나눈 나머지를 공백으로 구분하여 출력한다.

두 번째 줄에 $B_0,\cdots ,B_{N-1}$을 998ドル,円 244,円 353$으로 나눈 나머지를 공백으로 구분하여 출력한다.

제한

노트

유리수를 기약분수로 나타냈을 때 $\frac{a}{b}$인 경우 이 수를 소수인 $p$로 나눈 나머지는 $a\equiv c\cdot b\pmod p$를 만족하는 0ドル$ 이상 $p$ 미만의 정수 $c$이며, $b$가 $p$의 배수가 아니라면 이 값은 유일하다.

이 문제에서는 가능한 모든 입력에 대해 $A_0,\cdots ,A_{N-1}$과 $B_0,\cdots ,B_{N-1}$이 유리수이고 각 수를 기약분수로 나타냈을 때 분모가 998ドル,円 244,円 353$의 배수가 아니라는 것을 증명할 수 있다.