시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB111100.000%

문제

TL;DR Permutation pattern is a permutation with 0 as a wildcard. You are given a permutation pattern. For each index, find its expected cycle size if a random permutation conforming to the pattern is chosen and output it modulo $998\,244\,353$.

And now five times as long, three times as formal

A permutation is an array $p$ of length $n$, such that $\forall_{i \neq j}: p_i \neq p_j, \forall_i: 1 \leq p_i \leq n$

The product of permutations $p$ and $q$ which have the same length, denoted as $p \cdot q$ is the permutation r of the same length as both $p$ and $q$, such that $\forall_i: r_i = p_{q_i}$

The power $p^k$ where $p$ is a permutation and $k$ is a positive integer is

  1. $p$ if $k$ = 1
  2. $p^{k-1} \cdot p$ otherwise

Cycle size of index i is the minimal positive integer k, such that $(p^k)_i = i$. It can be shown that such number always exists.

Permutation pattern is an array of length $n$ such that $\forall_{i \neq j}: a_i = 0 or a_i \neq a_j, \forall_i: 0 \leq a_i \leq n$.

We say permutation $p$ conforms to the pattern $t$ if $\forall_i: p_i = t_i or t_i = 0$.

Let $ans_i$ be the expected cycle size of index i in a random permutation conforming to the pattern given in input. You are to find $ans_i$ modulo $998\,244\,353$.

Taking a potentially non-integer number $X$ modulo $M$ is the following procedure:

Jury guarantees that $X$ is equal to some irreducible fraction $\frac{P}{Q}$ where Q has an inverse modulo $M$. In that case $X$ modulo $M = A$, where $A$ is an integer between 0 and $M - 1$ inclusive and $P - QA$ is divisible by $M$. It can be shown that $A$ is unique.

입력

The first line contains one integer $n$ ($1 \leq n \leq 10^6$), the length of the permutation pattern.

The second line contains $n$ space separated integers $t_i$ ($0 \leq t_i \leq n$).

It is guaranteed that $t$ is a permutation pattern.

출력

Output $n$ integers. $i$-th of them must be equal to $ans_i$ modulo $998\,244\,353$.

예제 입력 1

5
2 3 4 5 0

예제 출력 1

5 5 5 5 5

예제 입력 2

2
0 0

예제 출력 2

499122178 499122178

예제 입력 3

6
3 0 1 6 5 2

예제 출력 3

2 3 2 3 1 3

노트

In the second example both $ans_i$ are equal to $\frac{3}{2}$ which equals 499122178 modulo 998244353.