← 返回题目列表

AtCoder · abc241_h

Ex. 卡组分数

中文机器翻译题面 查看原题

分数: 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.