[ABC241Ex] Card Deck Score

有一些卡牌，每张卡牌上有一个数字，具体的，有 $b_i$ 张卡牌上的数字为 $a_i$。 求出拿走其中 $m$ 张卡牌的贡献之和。贡献为这些卡牌的乘积。对于本质相同的卡牌组合，只算一次。 - $n\leq 16,m\leq 10^{18},b_i\leq 10^{17},1\leq a_i<mod$

[problemUrl]: https://atcoder.jp/contests/abc241/tasks/abc241_h $ N $ 個の整数のうちいずれか $ 1 $ つが書かれたカードが何枚かあり、 具体的には、$ A_i $ が書かれたカードが $ B_i $ 枚あります。 次に、この $ B_1+B_2\cdots\ +B_N $ 枚の中から $ M $ 枚のカードを選ぶ方法について、 その選んだカードに書かれた $ M $ 個の整数の積をその選び方のスコアとして定めます。 同じ整数が書かれたカードは区別できないとしたとき、$ M $ 枚の選び方としてあり得る すべての選び方についてスコアを足し合わせた値を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを出力せよ。

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\ \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 $ - 入力は全て整数である。 ### Sample Explanation 1 $ 3 $ 枚を選ぶ方法としては次の $ 6 $ 通りが考えられます。 - $ 3 $ と書かれたカードを $ 1 $ 枚、$ 5 $ と書かれたカードを $ 2 $ 枚選ぶ。 - $ 3 $ と書かれたカードを $ 1 $ 枚、$ 5 $ と書かれたカードを $ 1 $ 枚、$ 6 $ と書かれたカードを $ 1 $ 枚選ぶ。 - $ 3 $ と書かれたカードを $ 1 $ 枚、$ 6 $ と書かれたカードを $ 2 $ 枚選ぶ。 - $ 5 $ と書かれたカードを $ 2 $ 枚、$ 6 $ と書かれたカードを $ 1 $ 枚選ぶ。 - $ 5 $ と書かれたカードを $ 1 $ 枚、$ 6 $ と書かれたカードを $ 2 $ 枚選ぶ。 - $ 6 $ と書かれたカードを $ 3 $ 枚選ぶ。 スコアは順に $ 75 $, $ 90 $, $ 108 $, $ 150 $, $ 180 $, $ 216 $ であり、これらの総和は $ 819 $ となります。 ### Sample Explanation 2 「 $ 1 $ と $ 25 $ の書かれたカードを $ 1 $ 枚ずつ選ぶ」選び方と 「 $ 5 $ の書かれたカードを $ 2 $ 枚選ぶ」選び方は、いずれもスコアは $ 25 $ ですが、 カードの選び方としては異なるものとして数えられます。 ### Sample Explanation 3 $ 998244353 $ で割った余りを出力することに注意してください。