Score : $600$ points

问题描述

存在一些卡片，每张卡片上都写有一个来自 $N$ 个整数中的一个。具体来说，有 $B_i$ 张卡片上面写着整数 $A_i$。

接下来，对于从这 $(B_1+B_2+\cdots+B_N)$ 张卡片中选出的 $M$ 张卡片的组合，我们定义该组合的得分是这 $M$ 张卡片上所写整数的乘积。

假设写有相同整数的卡片是不可区分的，求所有可能的 $M$ 张卡片组合的得分之和，对 $998244353$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are some cards. Each card has one of $N$ integers written on it. Specifically, there are $B_i$ cards with $A_i$ written on them.
Next, for a combination of $M$ cards chosen out of these $(B_1+B_2\cdots +B_N)$ cards, we define the score of the combination by the product of the integers written on the $M$ cards.
Supposed that cards with the same integer written on them are indistinguishable, find the sum, modulo $998244353$, of the scores over all possible combinations of $M$ cards.

Constraints

• $1 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq A_i < 998244353$
• $1 \leq B_i \leq 10^{17}$
• If $i\neq j$, then $A_i \neq A_j$.
• $M\leq B_1+B_2+\cdots B_N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

Output

Print the answer.

Sample Input 1

3 3
3 1
5 2
6 3

Sample Output 1

819

There are $6$ possible combinations of $3$ cards.

• A combination of $1$ card with $3$ written on it, and $2$ cards with $5$ written on them.
• A combination of $1$ card with $3$ written on it, $1$ card with $5$ written on it, and $1$ card with $6$ written on it.
• A combination of $1$ card with $3$ written on it, and $2$ cards with $6$ written on them.
• A combination of $2$ cards with $5$ written on them, and $1$ card with $6$ written on it.
• A combination of $1$ card with $5$ written on it, and $2$ cards with $6$ written on them.
• A combination of $3$ cards with $6$ written on them.

The scores are $75$, $90$, $108$, $150$, $180$, and $216$, respectively, for a sum of $819$.

Sample Input 2

3 2
1 1
5 2
25 1

Sample Output 2

180

"A combination of a card with $1$ and another card with $25$" and "a combination of two cards with $5$ written on them" have the same score of $25$, but they are considered to be different combinations.

Sample Input 3

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

Sample Output 3

39761306

Be sure to print the answer modulo $998244353$.

update @ 2024/3/10 10:24:34