题意

已知有 $n$ 种物品，第 $i$ 种物品的价值都是 $a_i$，一共有 $b_i$ 个。

现在拿出 $m$ 个物品，总价值为选的物品的价值的乘积。

问所有选取方案的和，注意同种物品被视作是相同的。

答案对 $998244353$ 取模。

输入格式

一行一个数 $n$。

接下来 $n$ 行，每行两个数 $a_i,b_i$。

输出格式

一行一个数，表示答案。

样例

3 3
3 1
5 2
6 3

819

3 2
1 1
5 2
25 1

180

10 232657150901347497
139547946 28316250877914575
682142538 78223540024979445
110643588 74859962623690081
173455495 60713016476190629
271056265 85335723211047202
801329567 48049062628894325
864844366 54979173822804784
338794337 69587449430302156
737638908 15812229161735902
462149872 49993004923078537

39761306

数据范围

$1\le n\le 17$

$1\le m\le 10^{18}$

$1\le a_i< 998244353$

$1\le b_i\le 10^{17}$

$\sum b_i\ge m$