配点 : $600$ 点

問題文

$N$ 個の整数のうちいずれか $1$ つが書かれたカードが何枚かあり、 具体的には、$A_i$ が書かれたカードが $B_i$ 枚あります。 次に、この $B_1+B_2\cdots +B_N$ 枚の中から $M$ 枚のカードを選ぶ方法について、 その選んだカードに書かれた $M$ 個の整数の積をその選び方のスコアとして定めます。 同じ整数が書かれたカードは区別できないとしたとき、$M$ 枚の選び方としてあり得る すべての選び方についてスコアを足し合わせた値を $998244353$ で割った余りを求めてください。

制約

• $1 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq A_i < 998244353$
• $1 \leq B_i \leq 10^{17}$
• $i\neq j$ ならば $A_i \neq A_j$
• $M\leq B_1+B_2+\cdots B_N$
• 入力は全て整数である。

入力

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

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

出力

答えを出力せよ。

3 3
3 1
5 2
6 3

819

$3$ 枚を選ぶ方法としては次の $6$ 通りが考えられます。

• $3$ と書かれたカードを $1$ 枚、$5$ と書かれたカードを $2$ 枚選ぶ。
• $3$ と書かれたカードを $1$ 枚、$5$ と書かれたカードを $1$ 枚、$6$ と書かれたカードを $1$ 枚選ぶ。
• $3$ と書かれたカードを $1$ 枚、$6$ と書かれたカードを $2$ 枚選ぶ。
• $5$ と書かれたカードを $2$ 枚、$6$ と書かれたカードを $1$ 枚選ぶ。
• $5$ と書かれたカードを $1$ 枚、$6$ と書かれたカードを $2$ 枚選ぶ。
• $6$ と書かれたカードを $3$ 枚選ぶ。

スコアは順に $75$, $90$, $108$, $150$, $180$, $216$ であり、これらの総和は $819$ となります。

3 2
1 1
5 2
25 1

180

「 $1$ と $25$ の書かれたカードを $1$ 枚ずつ選ぶ」選び方と 「 $5$ の書かれたカードを $2$ 枚選ぶ」選び方は、いずれもスコアは $25$ ですが、 カードの選び方としては異なるものとして数えられます。

10 232657150901347497
139547946 28316250877914575
682142538 78223540024979445
110643588 74859962623690081
173455495 60713016476190629
271056265 85335723211047202
801329567 48049062628894325
864844366 54979173822804784
338794337 69587449430302156
737638908 15812229161735902
462149872 49993004923078537

39761306

$998244353$ で割った余りを出力することに注意してください。