简而言之：置换模式是一个包含 $0$ 作为通配符的置换。给定一个置换模式，对于每个下标，求出如果从符合该模式的随机置换中选择一个，该下标所在循环的期望大小，并将其对 $998\,244\,353$ 取模后输出。

正式定义如下：

置换是一个长度为 $n$ 的数组 $p$，满足 $\forall i \neq j : p_i \neq p_j$ 且 $\forall i : 1 \leq p_i \leq n$。

长度相同的置换 $p$ 和 $q$ 的乘积，记作 $p \cdot q$，是另一个长度为 $n$ 的置换 $r$，满足 $\forall i : r_i = p_{q_i}$。

置换 $p$ 的 $k$ 次幂 $p^k$（其中 $k$ 为正整数）定义为： 1. 若 $k = 1$，则为 $p$。 2. 否则为 $p^{k-1} \cdot p$。

下标 $i$ 的循环大小是满足 $(p^k)_i = i$ 的最小正整数 $k$。可以证明这样的数总是存在的。

置换模式是一个长度为 $n$ 的数组，满足 $\forall i \neq j : a_i = 0$ 或 $a_i \neq a_j$，且 $\forall i : 0 \leq a_i \leq n$。

若对于所有 $i$ 都有 $p_i = t_i$ 或 $t_i = 0$，则称置换 $p$ 符合模式 $t$。

令 $ans_i$ 为下标 $i$ 在符合输入给定模式的随机置换中的期望循环大小。你需要求出 $ans_i$ 对 $998\,244\,353$ 取模的结果。

对一个可能的非整数 $X$ 进行模 $M$ 运算的过程如下： 题目保证 $X$ 等于某个不可约分数 $\frac{P}{Q}$，其中 $Q$ 在模 $M$ 意义下存在逆元。在这种情况下，$X \pmod M = A$，其中 $A$ 是 $0$ 到 $M-1$ 之间的整数，且 $P - QA$ 能被 $M$ 整除。可以证明 $A$ 是唯一的。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 10^6$)，表示置换模式的长度。 第二行包含 $n$ 个空格分隔的整数 $t_i$ ($0 \leq t_i \leq n$)。 保证 $t$ 是一个置换模式。

输出格式

输出 $n$ 个整数。第 $i$ 个整数应等于 $ans_i$ 对 $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

说明

在第二个样例中，两个 $ans_i$ 均等于 $\frac{3}{2}$，即 $499122178 \pmod{998244353}$。