/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君が社長を務める会社では、N 人の社員がおり、それぞれ番号 1 から N が割り振られています。この会社では D ヶ月にわたってボーナスを支給します。
各社員 i（1 \leq i \leq N）には「貢献度」を表す正整数 P_i が定められており、貢献度の合計を S = P_1 + P_2 + \cdots + P_N とします。
各月 j（1 \leq j \leq D）において、会社全体のボーナス原資は W_j です。この原資は、各社員の貢献度の比率に従って分配されます。すなわち、月 j に社員 i が受け取るボーナスの額は
\frac{P_i \times W_j}{S}
です。
D ヶ月が終了した後、社員 i が受け取ったボーナスの総額は
T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j
となります。
青木君は経理担当として、全社員のボーナス総額の 積
R = \prod_{i=1}^{N} T_i
を計算したいと考えています。
R は 0 以上の有理数です。R を既約分数 \frac{A}{B}（A \geq 0, B > 0, \gcd(A, B) = 1）で表してください。特に R = 0 のときは A = 0, B = 1 とします。
このとき、A \times B^{-1} \bmod 998244353 を求めてください。ここで B^{-1} は 998244353 を法とする B のモジュラ逆元を表します。
なお、この問題の制約のもとで B は 998244353 と互いに素であること、すなわちモジュラ逆元が常に存在することが保証されます。
制約
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq P_i \leq 10^9（1 \leq i \leq N）
- 0 \leq W_j \leq 10^9（1 \leq j \leq D）
- S = P_1 + P_2 + \cdots + P_N は 998244353 の倍数ではない。
- 入力はすべて整数である。
入力
N D P_1 P_2 \cdots P_N W_1 W_2 \cdots W_D
- 1 行目には、社員の人数 N と月数 D が、スペース区切りで与えられる。
- 2 行目には、各社員の貢献度 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
- 3 行目には、各月のボーナス原資 W_1, W_2, \ldots, W_D が、スペース区切りで与えられる。
出力
R を既約分数 \frac{A}{B} で表したときの A \times B^{-1} \bmod 998244353 の値を、0 以上 998244353 未満の整数として 1 行で出力せよ。
入力例 1
2 2 1 1 2 2
出力例 1
4
入力例 2
3 3 1 2 3 0 0 0
出力例 2
0
入力例 3
5 4 1 2 3 4 5 10 20 30 40
出力例 3
211088321
入力例 4
10 10 3 7 2 5 11 4 8 6 9 1 100 200 150 300 50 175 225 125 275 80
出力例 4
953616835
入力例 5
1 1 1 5
出力例 5
5
Score : 366 pts
Problem Statement
At the company where Takahashi serves as president, there are N employees, each assigned a number from 1 to N. This company pays bonuses over a period of D months.
Each employee i (1 \leq i \leq N) has a positive integer P_i representing their "contribution level," and the total contribution is S = P_1 + P_2 + \cdots + P_N.
In each month j (1 \leq j \leq D), the company's total bonus fund is W_j. This fund is distributed according to the ratio of each employee's contribution level. That is, the bonus amount that employee i receives in month j is
\frac{P_i \times W_j}{S}
After D months have concluded, the total bonus received by employee i is
T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j
Aoki, as the accounting manager, wants to compute the product of all employees' total bonuses:
R = \prod_{i=1}^{N} T_i
R is a non-negative rational number. Express R as an irreducible fraction \frac{A}{B} (A \geq 0, B > 0, \gcd(A, B) = 1). In particular, when R = 0, let A = 0 and B = 1.
Compute A \times B^{-1} \bmod 998244353, where B^{-1} denotes the modular inverse of B modulo 998244353.
It is guaranteed that under the constraints of this problem, B is coprime with 998244353, meaning the modular inverse always exists.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq D \leq 10^6
- 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
- 0 \leq W_j \leq 10^9 (1 \leq j \leq D)
- S = P_1 + P_2 + \cdots + P_N is not a multiple of 998244353.
- All input values are integers.
Input
N D P_1 P_2 \cdots P_N W_1 W_2 \cdots W_D
- The first line contains the number of employees N and the number of months D, separated by a space.
- The second line contains the contribution levels P_1, P_2, \ldots, P_N of each employee, separated by spaces.
- The third line contains the bonus funds W_1, W_2, \ldots, W_D for each month, separated by spaces.
Output
Output the value of A \times B^{-1} \bmod 998244353, where R is expressed as the irreducible fraction \frac{A}{B}, as a single integer between 0 (inclusive) and 998244353 (exclusive) on one line.
Sample Input 1
2 2 1 1 2 2
Sample Output 1
4
Sample Input 2
3 3 1 2 3 0 0 0
Sample Output 2
0
Sample Input 3
5 4 1 2 3 4 5 10 20 30 40
Sample Output 3
211088321
Sample Input 4
10 10 3 7 2 5 11 4 8 6 9 1 100 200 150 300 50 175 225 125 275 80
Sample Output 4
953616835
Sample Input 5
1 1 1 5
Sample Output 5
5