{"raw_statement":[{"iden":"problem statement","content":"There are $N$ candies arranged in a row from left to right.  \nEach candy has one of the following $10^9$ colors: Color $1$, Color $2$, $\\ldots$, Color $10^9$.  \nFor each $i = 1, 2, \\ldots, N$, the $i$\\-th candy from the left has Color $c_i$.\nTakahashi will choose $K$ from the $N$ candies and get those $K$ candies.  \nThere 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.\nBecause Takahashi wants to eat colorful candies, the more variety of colors his candies have, the happier he will be.  \nFor each scenario $K = 1, 2, \\ldots, N$, find the expected value of the number of different colors Takahashi's candies will have.  \nWe can prove that the sought value is a rational number. Print this rational number modulo $998244353$, as described in Notes."},{"iden":"notes","content":"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}$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5 \\times 10^4$\n*   $1 \\leq c_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$c_1$ $c_2$ $\\ldots$ $c_N$"},{"iden":"sample input 1","content":"3\n1 2 2"},{"iden":"sample output 1","content":"1\n665496237\n2\n\nWhen $K = 1$, he will get the $1$\\-st candy, $2$\\-nd candy, or $3$\\-rd candy. In any case, his candy will have one color, so the expected value of the number of different colors is $1$.\nWhen $K = 2$, he will get the $1$\\-st and $2$\\-nd candies, $2$\\-nd and $3$\\-rd candies, or $1$\\-st and $3$\\-rd candies.\n\n*   If he gets the $1$\\-st and $2$\\-nd candies, they have two different colors.\n*   If he gets the $2$\\-nd and $3$\\-rd candies, they have one color.\n*   If he gets the $1$\\-st and $3$\\-rd candies, they have two different colors.\n\nThus, the expected value of the number of different colors is $\\frac{1}{3} \\cdot 2 + \\frac{1}{3} \\cdot 1 + \\frac{1}{3} \\cdot 2 = \\frac{5}{3}$.  \nBe sure to print it modulo $998244353$ as described in Notes.\nWhen $K = 3$, he will always get the $1$\\-st, $2$\\-nd, and $3$\\-rd candies, which have two different colors, so the expected value of the number of different colors is $2$."},{"iden":"sample input 2","content":"11\n3 1 4 1 5 9 2 6 5 3 5"},{"iden":"sample output 2","content":"1\n725995895\n532396991\n768345657\n786495555\n937744700\n574746754\n48399732\n707846002\n907494873\n7"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}