33547번 - 조 나누기

$N$명의 BOJ 대학교 학생들을 조들로 나눠, 각자 조별 과제를 하게 하려고 한다. 그런데, 어떤 학생들은 싫어하는 학생이 한 명 존재해 그 학생과는 조원을 하지 않으려고 한다. $i$번 학생이 싫어하는 학생은 $A_i$번 학생이다. 단, $A_i=i$인 경우는 싫어하는 학생이 존재하지 않는 경우이다.

$1$부터 $N$까지의 각 $M$에 대해, 여러분은 모든 학생이 싫어하는 학생과는 같은 조가 되지 않도록 학생들을 비지 않은 $M$개의 조로 나누는 경우의 수를 구해야 한다. 조로 나누는 두 방법이 다르다는 것은 한 방법에서만 같은 조에 속하는 학생 쌍이 존재함을 의미한다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $A_1,\dots ,A_N$이 공백으로 구분되어 주어진다.

$M=1$부터 $N$까지 순서대로 학생들을 $M$개의 조로 나누는 경우의 수를 소수 $998244353$로 나눈 나머지를 공백으로 구분하여 출력한다.

• 주어지는 모든 수는 정수이다.
• $1\le N\le 500\, 000$
• $1\le A_i\le N$ $(1\le i\le N)$