/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
N 個の白いボールがあります。はじめに各ボールを赤か青どちらかの色で塗ります。
これら N 個の赤か青で塗られたボールを、M 個の区別できる箱のいずれかに入れます。
i 番目の箱に入っている赤、青のボールの数をそれぞれ a_i, b_i とします。
全てのボールの入れ方に対する \prod_{1\leq i \le M}|a_i-b_i| の総和を 998244353 で割ったあまりを求めて下さい。
ただし、2 つのボールの入れ方が異なるとは、ある i について a_i,b_i の少なくとも一方が異なることを言います。
特に、ボール同士は区別しないことに注意してください。
制約
- 1 \le N,M \le 10^7
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
2 1
出力例 1
4
箱 1 にボールを入れる方法は 3 通りあります。
赤と青のボールを 1 個ずつ入れる場合、 |a_1-b_1|=0 です。
赤と青どちらかを 2 個入れる場合、|a_1-b_1|=2 です。
よって、求めるべき答えは 0 + 2 + 2 = 4 となります。
入力例 2
5 7
出力例 2
0
入力例 3
10000000 5000000
出力例 3
965172629
Score : 600 points
Problem Statement
There are N white balls. First, you paint each ball red or blue.
Then, you place these N red or blue painted balls in one of M distinguishable boxes.
Let a_i and b_i be the number of red and blue balls in the i-th box, respectively.
Find the sum, modulo 998244353, of \prod_{1\leq i \le M}|a_i-b_i| over all ways to place the balls.
Here, two ways of placing balls are different if and only if at least one of a_i and b_i is different for some i.
Particularly, balls are not distinguished from each other.
Constraints
- 1 \le N,M \le 10^7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Output the answer.
Sample Input 1
2 1
Sample Output 1
4
There are three ways to place balls in box 1.
If you place one red ball and one blue ball, |a_1-b_1|=0.
If you place two red balls or two blue balls, |a_1-b_1|=2.
Therefore, the answer is 0 + 2 + 2 = 4.
Sample Input 2
5 7
Sample Output 2
0
Sample Input 3
10000000 5000000
Sample Output 3
965172629