/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
正整数 N, M が与えられます。各要素が 0 または 1 である N 行 M 列の行列 A は全部で 2^{NM} 個存在しますが、そのうち以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。
- 1 \leq a < c \leq N かつ 1 \leq b < d \leq M を満たす全ての整数の組 (a, b, c, d) について、A_{a, b} \times A_{c, d} \leq A_{a, d} \times A_{c, b} が成り立つ。
制約
- 1 \leq N, M \leq 400
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを 1 行に出力せよ。
入力例 1
2 2
出力例 1
13
条件は A_{1,1} \times A_{2,2} \leq A_{1,2} \times A_{2,1} です。\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} 以外の 13 個が条件を満たします。
入力例 2
1 30
出力例 2
75497471
2^{NM} 個すべての行列が条件を満たすので、2^{30} を 998244353 で割ったあまりである 75497471 を出力します。
入力例 3
400 400
出力例 3
412670892
Score : 900 points
Problem Statement
You are given positive integers N and M. Among the 2^{NM} matrices A with N rows and M columns where each element is 0 or 1, find the number, modulo 998244353, of ones that satisfy the following condition:
- A_{a, b} \times A_{c, d} \leq A_{a, d} \times A_{c, b} for every quadruple of integers (a, b, c, d) such that 1 \leq a < c \leq N and 1 \leq b < d \leq M.
Constraints
- 1 \leq N, M \leq 400
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer in a single line.
Sample Input 1
2 2
Sample Output 1
13
The condition is A_{1,1} \times A_{2,2} \leq A_{1,2} \times A_{2,1}. All 13 matrices other than \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} satisfy the condition.
Sample Input 2
1 30
Sample Output 2
75497471
All 2^{NM} matrices satisfy the condition, so print 2^{30} modulo 998244353, that is, 75497471.
Sample Input 3
400 400
Sample Output 3
412670892