102417: [AtCoder]ABC241 Ex - Card Deck Score
Description
Score : $600$ points
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$.
Input
题意翻译
有一些卡牌，每张卡牌上有一个数字，具体的，有 $b_i$ 张卡牌上的数字为 $a_i$。 求出拿走其中 $m$ 张卡牌的贡献之和。贡献为这些卡牌的乘积。对于本质相同的卡牌组合，只算一次。 - $n\leq 16,m\leq 10^{18},b_i\leq 10^{17},1\leq a_i<mod$Output
问题描述
有一些卡片。每张卡片上写有$N$个整数中的一个。
具体来说，有$B_i$张写有$A_i$的卡片。
接下来，对于从这$(B_1+B_2\cdots +B_N)$张卡片中选出的$M$张卡片的组合，我们定义该组合的分数为写在$M$张卡片上的整数的乘积。
假设写有相同整数的卡片是不可区分的，找出所有可能的$M$张卡片组合的分数之和，对$998244353$取模。
约束条件
- $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$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出，格式如下：
$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
输出
打印答案。
样例输入1
3 3 3 1 5 2 6 3
样例输出1
819
有$6$种可能的$3$张卡片的组合。
- 一种组合，其中包含一张写有$3$的卡片，两张写有$5$的卡片。
- 一种组合，其中包含一张写有$3$的卡片，一张写有$5$的卡片，一张写有$6$的卡片。
- 一种组合，其中包含一张写有$3$的卡片，两张写有$6$的卡片。
- 一种组合，其中包含两张写有$5$的卡片，一张写有$6$的卡片。
- 一种组合，其中包含一张写有$5$的卡片，两张写有$6$的卡片。
- 一种组合，其中包含三张写有$6$的卡片。
这些组合的分数分别为$75$、$90$、$108$、$150$、$180$和$216$，和为$819$。
样例输入2
3 2 1 1 5 2 25 1
样例输出2
180
"一种组合，其中包含一张写有$1$的卡片和另一张写有$25$的卡片"和"一种组合，其中包含两张写有$5$的卡片"具有相同的分数$25$，但被视为不同的组合。
样例输入3
10 232657150901347497 139547946 28316250877914575 682142538 78223540024979445 110643588 74859962623690081 173455495 60713016476190629 271056265 85335723211047202 801329567 48049062628894325 864844366 54979173822804784 338794337 69587449430302156 737638908 15812229161735902 462149872 49993004923078537
样例输出3
39761306
请确保对$998244353$取模后打印答案。