AT_abc241_h [ABC241Ex] Card Deck Score

有若干张卡片，每张卡片上写有 $N$ 个整数中的某一个。具体来说，写有 $A_i$ 的卡片有 $B_i$ 张。 接下来，从这 $B_1+B_2+\cdots+B_N$ 张卡片中选出 $M$ 张。对于选出的 $M$ 张卡片，将它们上面写的 $M$ 个整数的乘积定义为这种选法的分数。 当写有相同整数的卡片无法区分时，请计算所有可能的 $M$ 张卡片的选法的分数之和，并输出其对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_N$ $B_N$

请输出答案。

## 限制条件 - $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$ - 输入均为整数。 ## 样例解释 1 选择 $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$。 ## 样例解释 2 “选 $1$ 张写有 $1$ 的卡片和 $1$ 张写有 $25$ 的卡片”与“选 $2$ 张写有 $5$ 的卡片”这两种选法的分数都是 $25$，但作为不同的选法应分别计数。 ## 样例解释 3 请注意输出时要对 $998244353$ 取模。 由 ChatGPT 4.1 翻译