Leapfrogger

<strong>Notice: If you have played Battlegrounds in Hearthstone and know the mechanism of leapfrogger and Baron Rivendare, you can start at the fourth paragraph, but note that the context of the problem is simplified and may not be the same as what is in-game.</strong>

In the famous card-collecting game <i>Hearthstone</i>, there is a mode named <i>Battlegrounds</i>, based on the auto battler genre, and allows eight players to compete in each match by recruiting minions over several rounds. In Battlegrounds, there is a special minion named <strong>leapfrogger</strong>, which is a second-tier beast with stats 3/3, and has the deathrattle of <i>"Give a friendly beast +1/+1 and this deathrattle''</i>, which means that when this minion dies, it will randomly give a friendly beast (if there exists any) the effect of +1/+1 in stats and this same effect (i.e., when that friendly beast dies, it will randomly give a friendly beast +1/+1 and the same effect, et cetera).



An interesting thing about leapfrogger is that its deathrattle is <strong>stackable</strong>, i.e., a minion is allowed to have multiple, say $k$, deathrattles of the leapfrogger at the same time, then when this minion dies, it will randomly give a friendly beast(if there exists any) the effect of +1/+1 in stats and this same effect, <strong>repeated $k$ times.</strong> Note that in each of the $k$ times, the friendly beast is chosen <strong>independently</strong> at random. What makes things more interesting is a minion in Battlegrounds called <strong>Baron Rivendare</strong> that can double the effect of deathrattles when it is on the board. When Baron Rivendare is on the board, and a leapfrogger dies, its deathrattle is triggered and given to a random friendly beast, <strong>twice</strong>. If both deathrattles are given to the same friendly beast and that beast dies, still with Baron Rivendare on the board, each of the two deathrattles of leapfrogger on the beast is triggered twice, so that a total of four copies of the deathrattle of leapfrogger are triggered and given to a random friendly beast... The speed the deathrattle of leapfrogger spread when Baron Rivendare is on the board is quite insane and is what makes the "leapfrogger build" a possible and quite powerful strategy in Battlegrounds.

That is quite a lot for the background. Let's then make some simplifications. We assume the deathrattle of leapfrogger can be given to <strong>any minion</strong> instead of <strong>only to beasts</strong>. We also assume that <strong>ALL Deathrattles will be triggered $k$ times</strong> for the sake of the problem. The question is,

<ol>
<li> There are $n$ minions on the board with <strong>exactly one</strong> of them being leapfrogger. If you kill all the $n$ minions in a random order, how many times in expectation will the deathrattle of the leapfrogger be triggered? (Recall that all deathrattles will be triggered $k$ times), answer the question for all $k=2,3,...,m$ for some given parameter $m$. Note that the deathrattles on the last minion still count as triggered, even if they are not given to another minion. </li>
</ol>

The first line contains an integer $T(1\leq T\leq 10)$, denoting the number of test cases.

For each test case, the input consists of one line containing two integers $n,m$. $(1\leq n \lt 998244353, 2\leq m \leq 10^5)$, denoting the number of minions and the parameter, respectively.

For each test case, the output consists of $m-1$ lines, where on the $i$-th line, you should output a number denoting the expected number of times the deathrattle of leapfrogger is triggered when all deathrattles will be triggered $k=i+1$ times. Under the input constraints of the problem, it can be shown that the answer can be written as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers and $Q\not\equiv 0\pmod {998244353}$. You need to output $P\cdot Q^{-1}\pmod{998244353}$ as the answer, where $Q^{-1}\pmod{998244353}$ represents the modular inverse of $Q$ with respect to $998244353$.

1
3 2

6

2022“杭电杯”中国大学生算法设计超级联赛（9）