Ex - Card Deck Score Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個の整数のうちいずれか 1 つが書かれたカードが何枚かあり、 具体的には、A_i が書かれたカードが B_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

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 となります。

入力例 2

3 2
1 1
5 2
25 1

出力例 2

180

「 1 と 25 の書かれたカードを 1 枚ずつ選ぶ」選び方と 「 5 の書かれたカードを 2 枚選ぶ」選び方は、いずれもスコアは 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 で割った余りを出力することに注意してください。

Score : 600 points

Problem Statement

There are some cards. Each card has one of N integers written on it. Specifically, there are B_i cards with A_i written on them.
Next, for a combination of M cards chosen out of these (B_1+B_2\cdots +B_N) cards, we define the score of the combination by the product of the integers written on the M cards.
Supposed that cards with the same integer written on them are indistinguishable, find the sum, modulo 998244353, of the scores over all possible combinations of M cards.

Constraints

  • 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, then A_i \neq A_j.
  • M\leq B_1+B_2+\cdots B_N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer.

Sample Input 1

3 3
3 1
5 2
6 3

Sample Output 1

819

There are 6 possible combinations of 3 cards.

  • A combination of 1 card with 3 written on it, and 2 cards with 5 written on them.
  • A combination of 1 card with 3 written on it, 1 card with 5 written on it, and 1 card with 6 written on it.
  • A combination of 1 card with 3 written on it, and 2 cards with 6 written on them.
  • A combination of 2 cards with 5 written on them, and 1 card with 6 written on it.
  • A combination of 1 card with 5 written on it, and 2 cards with 6 written on them.
  • A combination of 3 cards with 6 written on them.

The scores are 75, 90, 108, 150, 180, and 216, respectively, for a sum of 819.

Sample Input 2

3 2
1 1
5 2
25 1

Sample Output 2

180

"A combination of a card with 1 and another card with 25" and "a combination of two cards with 5 written on them" have the same score of 25, but they are considered to be different combinations.

Sample Input 3

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

Sample Output 3

39761306

Be sure to print the answer modulo 998244353.