当前没有测试数据。

牌组得分

得分：$600$ 分

题目描述

给定一些牌。每张牌上都写有 $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$

输出

输出答案。

3 3
3 1
5 2
6 3

819

总共有 $6$ 种可能的 $3$ 张牌的组合。

• 一张写着 $3$ 的牌，和两张写着 $5$ 的牌。
• 一张写着 $3$ 的牌，一张写着 $5$ 的牌，和一张写着 $6$ 的牌。
• 一张写着 $3$ 的牌，和两张写着 $6$ 的牌。
• 两张写着 $5$ 的牌，和一张写着 $6$ 的牌。
• 一张写着 $5$ 的牌，和两张写着 $6$ 的牌。
• 三张写着 $6$ 的牌。

得分分别为 $75$，$90$，$108$，$150$，$180$，和 $216$，总和为 $819$。

3 2
1 1
5 2
25 1

180

"一张写着 $1$ 的牌和一张写着 $25$ 的牌的组合" 和 "两张写着 $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$ 取模后输出答案。