#208 Crush

Loading problem...

Preparing the statement, recent submissions, and submit form.

#208 Crush | DOJ

Authors: lunarlity

Statement

한가람고등학교에는 학생 $N$ 명이 있다. 학생들은 번호가 $1,2,\cdots,N$ 으로 중복 없이 매겨져 있다.

각 학생은 자기 자신을 제외한 정확히 한 명의 학생을 짝사랑한다. 선생님은 일부 학생에 대해서만 그 학생이 짝사랑하는 사람의 번호를 알고 있으며, 아직 알지 못하는 학생도 있다.

선생님은 모든 정보가 완성되었을 때, 정확히 $K$ 쌍의 학생이 서로 좋아하도록 만드는 가능한 경우의 수를 알고 싶다. 여기서 서로 좋아하는 한 쌍이란, 서로 다른 두 학생 $i,j$ 가 $i$ 는 $j$ 를 짝사랑하고 $j$ 는 $i$ 를 짝사랑하는 경우를 말한다.

각 테스트 케이스에 대해 $K=0,1,2,\cdots,N-1$ 각각에 대한 가능한 경우의 수를 구하여라. 가능한 경우의 수가 매우 클 수 있으므로, 답은 $998\ 244\ 353$ 으로 나눈 나머지를 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$T$ (테스트 케이스 $1$ ) (테스트 케이스 $2$ ) $\vdots$ (테스트 케이스 $N$ )

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$N$ $B_1$ $B_2$ $\cdots$ $B_N$

각 테스트 케이스에서 $B_i$ 는 $i$ 번 학생에 대한 정보를 의미한다. $B_i=-1$ 이면 $i$ 번 학생이 누구를 짝사랑하는지 아직 모른다는 뜻이다. $B_i \neq -1$ 이면 $i$ 번 학생은 $B_i$ 번 학생을 짝사랑한다는 뜻이다.

각 테스트 케이스마다 한 줄에 $N$ 개의 정수를 공백으로 구분하여 출력한다.

$i$ 번째 정수는 $K=i-1$ 일 때 가능한 경우의 수를 $998\ 244\ 353$ 으로 나눈 나머지여야 한다.

Input

3
3
2 -1 2
4
2 3 -1 -1
10
2 4 6 8 10 -1 -1 -1 -1 3

Output

2 0
4 0 0
1671 135 1 0 0 0 0 0 0

학생들의 성별은 생각하지 않도록 한다.