← 返回题目列表

AtCoder · tenka1_2013_final_a

A. 天下一有无

中文机器翻译题面 查看原题

問題文

天下一株式会社制造天下一级的物质「Tenkaitium」。
「Tenkaitium」是制造次世代量子计算机不可或缺的物质。
新人优也君被分配到「Tenkaitium」的运用、管理团队。
优也君被分配后的第一份工作是为了运搬,把「Tenkaitium」放入容器中。然而,「Tenkaitium」在接近一定量以上时会引发「Tenka」ni有一种特性,它会变成 tium。遗憾的是,“Tenka”nitium 没有产业价值。
因此,悠也君考虑将容器划分为 N \times M的格子,并将“Tenkaitium”放置,使得同一格子中不出现两个以上,“Tenkaitium”也不会放在纵向、横向或斜向相邻的格子中。


入力

输入是按以下格式从标准输入给出的。

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

出力

输出“Tenkaitium”在不纵向、横向或斜向相邻的情况下,放置一个或多个的放置方法有多少种。 {\rm mod}\ 1000000007 将结果在标准输出中输出一行。但是,通过旋转或翻转形成相同的布局也算作不同的布局。
另外,行的末尾需要换行。


入力例 1

2 2

出力例 1

4

如果有“Tenkaitium”的格子用■表示,没有的格子用□表示,则可以考虑以下 4 种布局。


入力例 2

3 2

出力例 2

10

下面 10 种布局。