C - 天下一二三パズル
Editorial
/


Time Limit: 2 sec / Memory Limit: 64 MB
問題文
パズル作家のショウヘイ君は、天下一級のプログラマであるあなたに、「あるパズル」を出題して対決することになった。
そのパズルは以下のようなルールを持つものだった。
- M \times N のマス目が用意されており、そのマスすべてに対して 1, 2, 3 のいずれかの数字を以下の条件を満たすように入れていく。
- 同じ行または同じ列にある同じ数字のマスの間には、そのマスの数字以上の個数のマスが存在する。
このパズルでの数字の配置の仕方が何通りあるかを答えよ。
ただし、回転や反転によって同じになる配置も別々のものとして数える。
例えば、3 \times 3 のマス目に対しては以下のような配置ができる。

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

図 2

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

図 4
入力
入力は以下の形式で標準入力から与えられる。
M N
- 横方向のマスの数 M と 縦方向のマスの数 N ( 1 \leq M, N \leq 10^6 ) が空白区切りで 1 行で与えられる。
部分点
- M, N \leq 4 の入力に正解すると、120 点満点に対して部分点として 40 点が与えられる。
- M, N \leq 100 の入力に正解すると、120 点満点に対して部分点として、さらに 20 点が与えられる。
出力
数字の配置の仕方が何通りあるかを標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
1 1
出力例 1
3
入力例 2
3 1
出力例 2
8