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.