题目描述

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

输入格式

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

答えを出力せよ。

题目大意

有一些卡牌，每张卡牌上有一个数字，具体的，有 $b_i$ 张卡牌上的数字为 $a_i$。

求出拿走其中 $m$ 张卡牌的贡献之和。贡献为这些卡牌的乘积。对于本质相同的卡牌组合，只算一次。

• $n\leq 16,m\leq 10^{18},b_i\leq 10^{17},1\leq a_i<mod$

3 3
3 1
5 2
6 3

819

3 2
1 1
5 2
25 1

180

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

39761306

提示

制約

• $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$
• 入力は全て整数である。

Sample Explanation 1

$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$ となります。

Sample Explanation 2

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

Sample Explanation 3

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