#P22604. [ABC241Ex] Card Deck Score

[ABC241Ex] Card Deck Score

题意

已知有 nn 种物品,第 ii 种物品的价值都是 aia_i,一共有 bib_i 个。

现在拿出 mm 个物品,总价值为选的物品的价值的乘积。

问所有选取方案的和,注意同种物品被视作是相同的。

答案对 998244353998244353 取模。

输入格式

一行一个数 nn

接下来 nn 行,每行两个数 ai,bia_i,b_i

输出格式

一行一个数,表示答案。

样例

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

数据范围

1n171\le n\le 17

1m10181\le m\le 10^{18}

1ai<9982443531\le a_i< 998244353

1bi10171\le b_i\le 10^{17}

bim\sum b_i\ge m