黑板上最初写着一个数字x。您重复以下操作固定次数:
1. 将当前写在黑板上的数字 x 擦掉
2.从[0, x]范围内均匀随机选择一个整数,写在黑板上
给定初始数的分布和步数,确定最终数的分布。
输入
第一行包含两个整数,N (1 ≤ N ≤ 105) — 黑板上写的最大数字 — 和 M (0 ≤ M ≤ 1018) — 要执行的步骤数。
第二行包含 N + 1 个整数 P0, P1, ..., PN (0 ≤ Pi < 998244353),其中 Pi 描述起始数字为 i 的概率。我们可以将这个概率表示为不可约分数 P / Q,然后 $$P_i \equiv PQ^{-1} \pmod{998244353}$$。保证所有 Pi 之和等于 1(模 998244353)。
输出
输出单行 N + 1 个整数,其中 Ri 是 M 步后最终数字为 i 的概率。可以证明,概率总是可以表示为不可约分数 P / Q。要求您输出 $$R_i \equiv PQ^{-1} \pmod{998244353}$$。
示例
输入 #1
2 1 0 0 1
输出 #1
332748118 332748118 332748118
输入 #2
2 2 0 0 1
输出 #2
942786334 610038216 443664157
输入 #3
9 350 3 31 314 3141 31415 314159 3141592 31415926 314159265 649178508
输出 #3
822986014 12998613 84959018 728107923 939229297 935516344 27254497 413831286 583600448 442738326
注意
在第一种情况下,我们从数字 2 开始。一步之后,它将是 0、1 或 2,每个概率为 1/3。
在第二种情况下,数字仍为 2,概率为 1/9。以 1/9 的概率,在第一轮中保持 2,在下一轮中变为 1,以 1/6 的概率在第一轮中变为 1,并在第二轮中保持不变。在所有其他情况下,最终整数都是 0。