A - 天下一有無 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB


問題文

天下一株式会社では、天下一級の物質「Tenkaitium」を製造している。
「Tenkaitium」は、次世代量子コンピューターの製造に欠かせない物質となっている。
新人のユウヤ君は、「Tenkaitium」の運用・管理チームに配属されることになった。
配属されてからのユウヤ君の初仕事は、運搬のため、容器に「Tenkaitium」を入れる作業をすることになった。しかし、「Tenkaitium」には、ある一定量以上が接近すると「Tenkanitium」に変化してしまうという特性がある。残念ながら「Tenkanitium」に産業的価値はない。
そこで、ユウヤ君は、容器を N \times Mのマスに区切り、「Tenkaitium」が同じマスに2つ以上入ったり、縦、横、ななめに隣り合あったマスに入ったりしないように配置することを考えた。


入力

入力は以下の形式で標準入力から与えられる。

N M
  • 1 \leq N,\ M \leq 15

出力

「Tenkaitium」を縦、横、ななめに隣り合わないように1つ以上配置する方法が何通りあるかを {\rm mod}\ 1000000007 で標準出力に1行で出力せよ。ただし、回転や反転によって同じになる配置も別々のものとする。
また、行の終端には改行が必要である。


入力例 1

2 2

出力例 1

4

「Tenkaitium」が有るマスを■、無いマスを□とすると以下の 4 通りの配置が考えられる。


入力例 2

3 2

出力例 2

10

以下の 10 通りの配置が考えられる。