問題文

パズル作家のショウヘイ君は、天下一級のプログラマであるあなたに、「あるパズル」を出題して対決することになった。

そのパズルは以下のようなルールを持つものだった。

• M \times N のマス目が用意されており、そのマスすべてに対して 1, 2, 3 のいずれかの数字を以下の条件を満たすように入れていく。
• 同じ行または同じ列にある同じ数字のマスの間には、そのマスの数字以上の個数のマスが存在する。

このパズルでの数字の配置の仕方が何通りあるかを答えよ。
ただし、回転や反転によって同じになる配置も別々のものとして数える。

例えば、3 \times 3 のマス目に対しては以下のような配置ができる。

図 1

縦または、横一列に 1 が 2 つ以上存在している場合は以下のように間に 1 マス以上空いていなければならない。

図 2

図 3

2 を配置する場合は 2 マス以上空いていなければならない。

図 4

入力例 1

1 1

出力例 1

3

入力例 2

3 1

出力例 2

8