卡牌得分

题目描述

有一些卡片,每张卡片上写着一个整数,共 $N$ 种。 具体地,写着 $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
⋮
A_N B_N

输出格式

输出答案。

样例

3 3
3 1
5 2
6 3

819

选 $3$ 张卡片的组合共有 $6$ 种。

• $1$ 张写着 $3$ 的卡片和 $2$ 张写着 $5$ 的卡片。
• $1$ 张写着 $3$ 的卡片、$1$ 张写着 $5$ 的卡片和 $1$ 张写着 $6$ 的卡片。
• $1$ 张写着 $3$ 的卡片和 $2$ 张写着 $6$ 的卡片。
• $2$ 张写着 $5$ 的卡片和 $1$ 张写着 $6$ 的卡片。
• $1$ 张写着 $5$ 的卡片和 $2$ 张写着 $6$ 的卡片。
• $3$ 张写着 $6$ 的卡片。

它们的得分分别为 $75$、$90$、$108$、$150$、$180$、$216$,总和为 $819$。

3 2
1 1
5 2
25 1

180

「由 $1$ 张写 $1$ 的卡片和 $1$ 张写 $25$ 的卡片组成的组合」与「由 $2$ 张写 $5$ 的卡片组成的组合」得分同为 $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$ 取模后的答案。

数据范围

• $1 \le N \le 16$
• $1 \le M \le 10^{18}$
• $1 \le A_i \lt 998244353$
• $1 \le B_i \le 10^{17}$
• 如果 $i\neq j$,则 $A_i \neq A_j$。
• $M \le B_1+B_2+\cdots +B_N$
• 输入中的所有值均为整数。