Colorful Candies 2

There are $N$ candies arranged in a row from left to right. Each candy has one of the following $10^9$ colors: Color $1$, Color $2$, $\ldots$, Color $10^9$. For each $i = 1, 2, \ldots, N$, the $i$\-th candy from the left has Color $c_i$. Takahashi will choose $K$ from the $N$ candies and get those $K$ candies. There are $\binom{N}{K}$ ways to choose $K$ from the $N$ candies, where $\binom{N}{K}$ is a binomial coefficient. Takahashi will randomly select one of these $\binom{N}{K}$ ways with equal probability. Because Takahashi wants to eat colorful candies, the more variety of colors his candies have, the happier he will be. For each scenario $K = 1, 2, \ldots, N$, find the expected value of the number of different colors Takahashi's candies will have. We can prove that the sought value is a rational number. Print this rational number modulo $998244353$, as described in Notes. ## Constraints * $1 \leq N \leq 5 \times 10^4$ * $1 \leq c_i \leq 10^9$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $c_1$ $c_2$ $\ldots$ $c_N$ [samples] ## Notes When you print a rational number, first write it as a fraction $\frac{y}{x}$, where $x, y$ are integers and $x$ is not divisible by $998244353$ (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer $z$ between $0$ and $P - 1$, inclusive, that satisfies $xz \equiv y \pmod{998244353}$.