I - Hypercube Interior Paths
ผักชี
2
s
1024
MB
1000
点
問題文
正の整数 $N, D$ が与えられます。各整数 $d = 1, 2, \ldots, D$ について、以下の問題を解いてください。
$d$ 次元空間において、各座標が $0$ 以上 $N$ 以下の整数であるような格子点 $(x_1, x_2, \ldots, x_d)$ 全体からなる集合を考えます。
あなたは最初、格子点 $(0, 0, \ldots, 0)$ にいます。ここから1回の移動で「いずれか1つの座標の値を $1$ 増やす」という操作を $Nd$ 回繰り返すことで、格子点 $(N, N, \ldots, N)$ へと向かう最短経路を考えます。
移動の途中で、内部の格子点を1回以上通るような最短経路の総数を $998244353$ で割った余りを求めてください。
ただし、内部の格子点とは、すべての整数 $i$($1 \leq i \leq d$)について $0 < x_i < N$ を満たす格子点 $(x_1, x_2, \ldots, x_d)$ のことを指します。
制約
- $2 \leq N$
- $1 \leq D \leq 2\times10^5$
- $ND \leq 5\times10^6$
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられます。
$N$ $D$
出力
$d = 1, 2, \ldots, D$ に対する答えをそれぞれ $A_1, A_2, \ldots, A_D$ とするとき、以下の形式で空白区切りで1行に出力してください。
$A_1$ $A_2$ $\ldots$ $A_D$
入力例 1
2 3
出力例 1
1 4 36
- $d = 1$ のとき、内部の格子点は $(1)$ のみであり、条件を満たす最短経路は $(0) \to (1) \to (2)$ の $1$ 通りです。
- $d = 2$ のとき、内部の格子点は $(1, 1)$ のみです。$(0, 0)$ から $(1, 1)$ への最短経路が $2$ 通り、$(1, 1)$ から $(2, 2)$ への最短経路が $2$ 通りあるため、条件を満たす最短経路は $2 \times 2 = 4$ 通りです。
- $d = 3$ のとき、内部の格子点は $(1, 1, 1)$ のみです。$(0, 0, 0)$ から $(1, 1, 1)$ への最短経路が $6$ 通り、$(1, 1, 1)$ から $(2, 2, 2)$ への最短経路が $6$ 通りあるため、条件を満たす最短経路は $6 \times 6 = 36$ 通りです。
入力例 2
5 4
出力例 2
1 250 740250 280688117
$998244353$ で割った余りを出力してください。