{"raw_statement":[{"iden":"statement","content":"There is a number _x_ initially written on a blackboard. You repeat the following action a fixed amount of times:\n\n1.  take the number _x_ currently written on a blackboard and erase it\n2.  select an integer uniformly at random from the range \\[0, _x_\\] inclusive, and write it on the blackboard\n\nDetermine the distribution of final number given the distribution of initial number and the number of steps."},{"iden":"input","content":"The first line contains two integers, _N_ (1 ≤ _N_ ≤ 105) — the maximum number written on the blackboard — and _M_ (0 ≤ _M_ ≤ 1018) — the number of steps to perform.\n\nThe second line contains _N_ + 1 integers _P_0, _P_1, ..., _P__N_ (0 ≤ _P__i_ < 998244353), where _P__i_ describes the probability that the starting number is _i_. We can express this probability as irreducible fraction _P_ / _Q_, then . It is guaranteed that the sum of all _P__i_s equals 1 (modulo 998244353)."},{"iden":"output","content":"Output a single line of _N_ + 1 integers, where _R__i_ is the probability that the final number after _M_ steps is _i_. It can be proven that the probability may always be expressed as an irreducible fraction _P_ / _Q_. You are asked to output ."},{"iden":"examples","content":"Input\n\n2 1\n0 0 1\n\nOutput\n\n332748118 332748118 332748118\n\nInput\n\n2 2\n0 0 1\n\nOutput\n\n942786334 610038216 443664157\n\nInput\n\n9 350\n3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508\n\nOutput\n\n822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326"},{"iden":"note","content":"In the first case, we start with number 2. After one step, it will be 0, 1 or 2 with probability 1/3 each.\n\nIn the second case, the number will remain 2 with probability 1/9. With probability 1/9 it stays 2 in the first round and changes to 1 in the next, and with probability 1/6 changes to 1 in the first round and stays in the second. In all other cases the final integer is 0."}],"translated_statement":[{"iden":"statement","content":"黑板上最初写有一个数字 #cf_span[x]。你将重复以下操作固定次数：\n\n给定初始数字的分布和操作步数，求最终数字的分布。\n\n第一行包含两个整数，#cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 黑板上可能写出的最大数字，以及 #cf_span[M] (#cf_span[0 ≤ M ≤ 1018]) —— 要执行的操作步数。\n\n第二行包含 #cf_span[N + 1] 个整数 #cf_span[P0, P1, ..., PN] (#cf_span[0 ≤ Pi < 998244353])，其中 #cf_span[Pi] 表示初始数字为 #cf_span[i] 的概率。我们可以将该概率表示为最简分数 #cf_span[P / Q]，则 。保证所有 #cf_span[Pi] 之和等于 #cf_span[1]（模 #cf_span[998244353]）。\n\n请输出一行 #cf_span[N + 1] 个整数，其中 #cf_span[Ri] 表示经过 #cf_span[M] 步后最终数字为 #cf_span[i] 的概率。可以证明，该概率总能表示为最简分数 #cf_span[P / Q]。你需输出 。\n\n在第一个例子中，我们从数字 2 开始。经过一步后，它将以各 1/3 的概率变为 0、1 或 2。\n\n在第二个例子中，数字以概率 1/9 保持为 2。以概率 1/9，它在第一轮保持为 2，第二轮变为 1；以概率 1/6，它在第一轮变为 1，第二轮保持不变。在所有其他情况下，最终整数为 0。\n\n"},{"iden":"input","content":"第一行包含两个整数，#cf_span[N] (#cf_span[1 ≤ N ≤ 105]) —— 黑板上可能写出的最大数字，以及 #cf_span[M] (#cf_span[0 ≤ M ≤ 1018]) —— 要执行的操作步数。第二行包含 #cf_span[N + 1] 个整数 #cf_span[P0, P1, ..., PN] (#cf_span[0 ≤ Pi < 998244353])，其中 #cf_span[Pi] 表示初始数字为 #cf_span[i] 的概率。我们可以将该概率表示为最简分数 #cf_span[P / Q]，则 。保证所有 #cf_span[Pi] 之和等于 #cf_span[1]（模 #cf_span[998244353]）。"},{"iden":"output","content":"请输出一行 #cf_span[N + 1] 个整数，其中 #cf_span[Ri] 表示经过 #cf_span[M] 步后最终数字为 #cf_span[i] 的概率。可以证明，该概率总能表示为最简分数 #cf_span[P / Q]。你需输出 。"},{"iden":"examples","content":"输入：\n2 1\n0 0 1\n输出：\n332748118 332748118 332748118\n\n输入：\n2 2\n0 0 1\n输出：\n942786334 610038216 443664157\n\n输入：\n9 35\n0 3 31 314 3141 31415 314159 3141592 31415926 314159265\n输出：\n822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326"},{"iden":"note","content":"在第一个例子中，我们从数字 2 开始。经过一步后，它将以各 1/3 的概率变为 0、1 或 2。\n\n在第二个例子中，数字以概率 1/9 保持为 2。以概率 1/9，它在第一轮保持为 2，第二轮变为 1；以概率 1/6，它在第一轮变为 1，第二轮保持不变。在所有其他情况下，最终整数为 0。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ \\mathbf{P} = (P_0, P_1, \\dots, P_N) \\in \\mathbb{F}_{998244353}^{N+1} $ be the initial probability distribution, where $ P_i = \\mathbb{P}(\\text{initial number} = i) $.  \nLet $ \\mathbf{R}^{(M)} = (R_0^{(M)}, R_1^{(M)}, \\dots, R_N^{(M)}) \\in \\mathbb{F}_{998244353}^{N+1} $ be the final probability distribution after $ M $ steps.\n\nLet $ T \\in \\mathbb{F}_{998244353}^{(N+1) \\times (N+1)} $ be the transition matrix defined by:  \n$$\nT_{i,j} = \\mathbb{P}(\\text{next number} = j \\mid \\text{current number} = i) = \n\\begin{cases}\n\\frac{1}{i+1} & \\text{if } 0 \\leq j \\leq i \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 0 \\leq M \\leq 10^{18} $  \n3. $ \\sum_{i=0}^N P_i \\equiv 1 \\pmod{998244353} $  \n4. $ 0 \\leq P_i < 998244353 $ for all $ i $\n\n**Objective**  \nCompute:  \n$$\n\\mathbf{R}^{(M)} = \\mathbf{P}^\\top \\cdot T^M\n$$  \nOutput $ R_0^{(M)}, R_1^{(M)}, \\dots, R_N^{(M)} $ modulo $ 998244353 $.","simple_statement":null,"has_page_source":false}