問題文
天下一株式会社制造天下一级的物质「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 种布局。