기대 사이클 크기

TL;DR: 순열 패턴은 0을 와일드카드로 쓰는 순열이다. 순열 패턴 $t$가 주어지면, 각 인덱스 $i$에 대해 $t$를 따르는 임의의 순열을 골랐을 때 인덱스 $i$의 기대 사이클 크기를 구하고, 그 값을 $998244353$으로 나눈 나머지를 출력한다.

순열은 길이가 $n$인 배열 $p$로서, $\forall_{i \neq j}: p_i \neq p_j$이고 $\forall_i: 1 \leq p_i \leq n$을 만족한다.

길이가 같은 두 순열 $p$, $q$의 곱 $p \cdot q$는 길이가 같은 순열 $r$이며, $\forall_i: r_i = p_{q_i}$를 만족한다.

순열 $p$와 양의 정수 $k$에 대한 거듭제곱 $p^k$는 다음과 같이 정의한다. $k = 1$이면 $p^k = p$이고, 그 밖의 경우에는 $p^k = p^{k-1} \cdot p$이다.

인덱스 $i$의 사이클 크기는 $(p^k)_i = i$를 만족하는 가장 작은 양의 정수 $k$이다. 이러한 $k$는 항상 존재함이 알려져 있다.

순열 패턴은 길이가 $n$인 배열 $a$로서, $\forall_{i \neq j}: a_i = 0 \lor a_i \neq a_j$이고 $\forall_i: 0 \leq a_i \leq n$을 만족한다.

순열 $p$가 패턴 $t$를 따른다는 것은, 모든 $i$에 대해 $p_i = t_i$ 또는 $t_i = 0$이 성립한다는 뜻이다.

$ans_i$는 주어진 패턴을 따르는 임의의 순열에서 인덱스 $i$의 기대 사이클 크기이다. $ans_i$를 $998244353$으로 나눈 나머지를 구하라.

유리수 $X$를 $M$으로 나눈 나머지는 다음과 같이 정한다. 심사위원은 $X$가 어떤 기약분수 $\frac{P}{Q}$와 같고, $Q$가 $M$에 대한 역원을 가짐을 보장한다. 이때 $X$를 $M$으로 나눈 나머지는 $0$ 이상 $M-1$ 이하의 정수 $A$로서, $P - QA$가 $M$으로 나누어떨어지는 값이다. 이러한 $A$는 하나뿐이다.

첫째 줄에 패턴의 길이 $n$ ($1 \leq n \leq 10^6$)이 주어진다.

둘째 줄에는 공백으로 구분된 정수 $t_i$ ($0 \leq t_i \leq n$) $n$개가 주어진다. 입력은 순열 패턴임이 보장된다.

정수 $n$개를 출력한다. $i$번째 정수는 $ans_i$를 $998244353$으로 나눈 나머지이다.

두 번째 예제에서 모든 $ans_i$는 $\frac{3}{2}$이며, 이를 $998244353$으로 나눈 나머지는 499122178이다.