AT_agc050_d [AGC050D] Shopping

[problemUrl]: https://atcoder.jp/contests/agc050/tasks/agc050_d $ 1 $ から $ N $ までの番号が振られた $ N $ 人の人と、$ 1 $ から $ K $ までの番号が振られた $ K $ 個の商品があります。 これから、ターン制のゲームが行われます。 ターンは、番号 $ 1 $ の人、番号 $ 2 $ の人、番号 $ 3 $ の人、$ \ldots $、番号 $ N $ の人、番号 $ 1 $ の人 、$ \ldots $、番号 $ N $ の人、番号 $ 1 $ の人、$ \ldots $、の順に回り、全ての商品が誰かに獲得されるまで続きます。 各ターンには、以下が行われます。 - 自分のターンが来た人がすでに商品を獲得済みの場合、何も行われない。 - そうでない場合、その人は、まだ自分が選んでいない商品から $ 1 $ つを等確率でランダムに選び、審判であるすぬけ君に秘密裏に伝える。 その商品がすでに他の誰かに獲得されていたなら、何も起こらない。そうでないなら、その商品はその人が獲得する。 各 $ i $ について、番号 $ i $ の人がいずれかの商品を獲得する確率を $ \bmod\ 998,244,353 $ で計算してください (注記参照)。

入力は標準入力から以下の形式で与えられる。 > $ N $ $ K $

$ N $ 行出力せよ。 $ i $ 行目には、番号 $ i $ の人がいずれかの商品を獲得する確率を $ \bmod\ 998,244,353 $ で出力すること。

### 注記 - 商品をランダムに選ぶ行為は全て独立に行われます。 - ゲームが有限のターン数で終了することは証明可能です。 - 参加者が商品を選ぶ場面で、まだその人が選んでいない商品が必ず $ 1 $ つ以上存在することも証明可能です。 - 求めるべき確率が有理数であることも証明可能です。確率を出力する際は、まずその確率を分数 $ \frac{y}{x} $ として表してください。ここで、$ x,\ y $ は整数であり、$ x $ は $ P\ =\ 998,244,353 $ で割り切れてはなりません (この問題の制約の下で、そのような表現は必ず可能です)。そして、$ xz\ \equiv\ y\ \pmod{P} $ なる $ 0 $ 以上 $ P\ -\ 1 $ 以下の唯一の整数 $ z $ を出力してください。 ### 制約 - $ 1\ \leq\ K\ \leq\ N\ \leq\ 40 $ - 入力中の全ての値は整数である。 ### Sample Explanation 1 \- まず、番号 $ 1 $ の人が商品を $ 1 $ 個選んで獲得します。ここで商品 $ p $ が選ばれたとします。 - そして、$ 1/2 $ の確率で、番号 $ 2 $ の人がもう一方の商品を選んで獲得し、ゲームが終了します。 - $ 1/2 $ の確率で、番号 $ 2 $ の人も商品 $ p $ を選んでしまって獲得できず、番号 $ 3 $ の人のターンとなります。 - $ 1/4 $ の確率で、番号 $ 3 $ の人がもう一方の商品を選んで獲得し、ゲームが終了します。 - $ 1/4 $ の確率で、番号 $ 3 $ の人も商品 $ p $ を選んでしまいます。その次は番号 $ 1 $ の人のターンですが、商品を獲得済みのため何もしません。その次は番号 $ 2 $ の人のターンであり、商品 $ p $ は前回選んだため今回は必ずもう一方の商品を選んで獲得し、ゲームが終了します。 以上より、番号 $ 1,\ 2,\ 3 $ の人がいずれかの商品を獲得する確率はそれぞれ $ 1,\ \frac{3}{4},\ \frac{1}{4} $ です。 ### Sample Explanation 2 商品獲得確率はそれぞれ $ 1,\ \frac{47}{54},\ \frac{77}{108},\ \frac{5}{12} $ です。