問題ヴィジュアル

イントロダクション

承認欲求にまみれた SNS の奴隷が $1$ 人, また $1$ 人と生まれていく...

問題文

サクラックスという SNS には, $1$ つのメッセージにつき, $N$ 個の指標がある. なお, 各指標は $0$ 以上の実数を取る.

サクラックスのユーザーであるチェリーちゃんはサクラックスにメッセージを投稿することによって, 承認欲求を満たしている.

メッセージのそれぞれの指標について, $i$ 番目の指標は $k_i$ を形状パラメータ, $a_i$ を尺度パラメータとする Erlang 分布に従う.

つまり, $i$ 番目の指標は以下のように実数上で定義される関数 $f_i(x)$ を確率密度関数に持つ. $$f_i(x)=\begin{cases} \dfrac{1}{(k_i-1)! a_i^{k_i} } x^{k_i-1} e^{-x/a_i} & (x \geq 0) \\ 0 & (x < 0)\end{cases}$$

また, $N$ 個ある指標はそれぞれ独立である.

$m = 1, 2, \dots, N$ それぞれに対して, 以下の問に答えよ.

チェリーちゃんがメッセージを投稿して満たされる承認欲求の大きさは $N$ 個ある指標のうち, 小さい方から $m$ 番目の値 (昇順 $m$ 番目) と等しい.

チェリーちゃんがメッセージを投稿して満たされる承認欲求の大きさの期待値を $E_m$ としたとき, $E_m \pmod{998244353}$ を求めよ.

注記

この問題の制約下では, $m=1,2, \dots, N$ それぞれに対して, 以下を満たすような整数の組 $(X,Y)$ が存在することが証明できる.

• $Y$ は $998244353$ の倍数ではない.
• $Y \times E_m = X$.

この条件を満たすような整数の組 $X,Y$ に対して, $$Y \times Z \equiv X \pmod{998244353}$$ となる $0$ 以上 $998244353$ 未満の整数 $Z$ が唯一存在するので, この整数 $Z$ を用いて, $E_m \pmod{998244353}:=Z$ と定義する.

なお, 条件を満たすような整数の組 $(X,Y)$ は数多に考えられるが, $Z$ は $X,Y$ の取り方に依らず, $E_m$ のみによって決定する.

制約

• $1 \leq N \leq 12$.
• $1 \leq k_i \quad (1 \leq i \leq N)$.
• $k_1+\dots+k_N \leq 4000$.
• $1 \leq a_i \leq 20 \quad (1 \leq i \leq N)$.
• 入力は全て整数である.

入力

$N$
$k_1$ $a_1$
$k_2$ $a_2$
$\vdots$
$k_N$ $a_N$

出力

$m=1,2, \dots, N$ の順に $E_m \pmod{998244353}$ を空白切りで $1$ 行で出力せよ.

最後に改行を忘れないこと.

サンプル

2
1 2
2 3

439227517 559016844

1
4 6

24

10
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

231989476 767777666 541286442 413771015 956738398 132234121 836358717 542139458 434737454 134190448