分数: 600 点
问题陈述
有一些卡片。 每张卡都有一个 N 上面写着整数。
具体来说,有 B_i 卡片
上面写着 A_i 。
接下来,对于以下组合
从这些卡片中选择的 M 卡片 (B_1+B_2\cdots +B_N) 卡片,
我们通过写在上面的整数的乘积来定义组合的分数 M 卡。
假设写有相同整数的卡片无法区分,
求总和,取模 998244353,所有可能组合的分数 M 卡。
约束
- 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,那么 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 卡。
- 的组合 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
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.