Grid Graph Maximum Matching Sum

You are given a two-dimensional plane with integer coordinate points. Consider all points \((x,y)\) such that \(1\le x\le n\) and \(1\le y\le m\). No two points share the same coordinates.

For any nonempty subset of these points, we construct a graph as follows: for every two distinct points, if they share the same horizontal coordinate (row) or vertical coordinate (column), add an edge between them. In other words, for any two points \((x_i,y_i)\) and \((x_j,y_j)\) in the subset, an edge is present if either \(x_i=x_j\) or \(y_i=y_j\).

A matching in a graph is a set of edges no two of which share a common vertex. The maximum matching is one with the largest number of edges. For example, if the subset contains only one point the maximum matching size is 0; if it contains two points and they lie in the same row (or column) then the maximum matching has size 1; if they do not share a row or column then no edge exists and the maximum matching size is 0.

Your task is to compute the sum of the maximum matching sizes over all nonempty subsets of the points in the \(n\times m\) grid, and output the answer modulo \(998244353\).

The input consists of two integers \(n\) and \(m\). It is guaranteed that the grid size is small enough to allow an algorithm with time complexity proportional to \(2^{nm}\) (for example, \(n,m\le 4\)).

Note: If a subset contains several points, the matching is chosen from the set of all edges between points that share a row or column such that no point is incident to more than one edge in the matching.

The problem may be formally described as follows:

Given all subsets \(S\) (with \(S\ne \emptyset\)) of the set of points \(\{(x,y) \mid 1\le x\le n,\, 1\le y\le m\}\), let \(f(S)\) be the size (i.e. number of edges) of a maximum matching in the graph induced by \(S\) (with edges only between points sharing the same x or y coordinate). Compute \[ \sum_{\emptyset\ne S\subseteq [n]\times[m]} f(S) \pmod{998244353}. \]

inputFormat

The first line of input contains two integers \(n\) and \(m\) (\(1\le n,m\le 4\)).

outputFormat

Output a single integer: the sum of the maximum matching sizes over all nonempty subsets of the points modulo \(998244353\).

sample

1 1

0