/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1800 点
問題文
N 行 M 列のマス目があります。高橋君は、以下のようにして各マスに整数を書き込みます。
- まず、すべてのマスに 0 を書き込む
- i=1,2,...,N に対し、整数 k_i (0\leq k_i\leq M) を選び、上から i 行目の左から k_i 個のマスに書かれた整数すべてに 1 を足す
- j=1,2,...,M に対し、整数 l_j (0\leq l_j\leq N) を選び、左から j 列目の上から l_j 個のマスに書かれた整数すべてに 1 を足す
こうして、各マスに 0,1,2 のいずれかの整数の書かれたマス目が出来上がります。最終的にできる可能性のある相異なるマス目の個数を 998244353 で割った余りを求めてください。 ただし、2 つのマス目が異なるとは、あるマスが存在してそのマスに書かれた整数が異なることを指します。
制約
- 1 \leq N,M \leq 5\times 10^5
- N,M は整数である
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
最終的にできる可能性のある相異なるマス目の個数を 998244353 で割った余りを出力せよ。
入力例 1
1 2
出力例 1
8
左のマスに a が、右のマスに b が書き込まれたマス目を (a,b) と表すことにすると、(0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) の 8 通りのマス目ができる可能性があります。
入力例 2
2 3
出力例 2
234
入力例 3
10 7
出力例 3
995651918
入力例 4
314159 265358
出力例 4
70273732
Score : 1800 points
Problem Statement
We have a square grid with N rows and M columns. Takahashi will write an integer in each of the squares, as follows:
- First, write 0 in every square.
- For each i=1,2,...,N, choose an integer k_i (0\leq k_i\leq M), and add 1 to each of the leftmost k_i squares in the i-th row.
- For each j=1,2,...,M, choose an integer l_j (0\leq l_j\leq N), and add 1 to each of the topmost l_j squares in the j-th column.
Now we have a grid where each square contains 0, 1, or 2. Find the number of different grids that can be made this way, modulo 998244353. We consider two grids different when there exists a square with different integers.
Constraints
- 1 \leq N,M \leq 5\times 10^5
- N and M are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the number of different grids that can be made, modulo 998244353.
Sample Input 1
1 2
Sample Output 1
8
Let (a,b) denote the grid where the square to the left contains a and the square to the right contains b. Eight grids can be made: (0,0),(0,1),(1,0),(1,1),(1,2),(2,0),(2,1), and (2,2).
Sample Input 2
2 3
Sample Output 2
234
Sample Input 3
10 7
Sample Output 3
995651918
Sample Input 4
314159 265358
Sample Output 4
70273732