/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および長さ M の正整数列 B=(B_1,B_2,\dots,B_M) が与えられます。
\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \binom{A_i}{B_j} の値を 998244353 で割った余りを求めてください。
ここで、\displaystyle \binom{x}{y} は x 個のものの中から y 個のものを選ぶ場合の数（二項係数）を表し、特に x < y のときは 0 です。
制約
- 1\leq N,M \leq 5\times 10^5
- 1\leq A_i,B_j \leq 5\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
出力
答えを出力せよ。
入力例 1
3 2 2 5 4 1 3
出力例 1
25
答えは \displaystyle \binom{2}{1}+\binom{2}{3}+\binom{5}{1}+\binom{5}{3}+\binom{4}{1}+\binom{4}{3}=2+0+5+10+4+4=25 です。
入力例 2
4 4 2 5 1 5 2 1 2 4
出力例 2
65
入力例 3
6 8 203497 47202 407775 394325 463982 304784 468417 302156 131932 235902 395728 78537 223857 330739
出力例 3
602855848
Score : 575 points
Problem Statement
You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a sequence of positive integers B=(B_1,B_2,\dots,B_M) of length M.
Find the value of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \binom{A_i}{B_j}, modulo 998244353.
Here, \displaystyle \binom{x}{y} represents the number of ways to choose y objects from x objects (binomial coefficient), and particularly, it is 0 if x < y.
Constraints
- 1\leq N,M \leq 5\times 10^5
- 1\leq A_i,B_j \leq 5\times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
Output
Output the answer.
Sample Input 1
3 2 2 5 4 1 3
Sample Output 1
25
The answer is \displaystyle \binom{2}{1}+\binom{2}{3}+\binom{5}{1}+\binom{5}{3}+\binom{4}{1}+\binom{4}{3}=2+0+5+10+4+4=25.
Sample Input 2
4 4 2 5 1 5 2 1 2 4
Sample Output 2
65
Sample Input 3
6 8 203497 47202 407775 394325 463982 304784 468417 302156 131932 235902 395728 78537 223857 330739
Sample Output 3
602855848