题目描述

有一些卡片，每张卡片上写着 $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$ 的模。