P5005 中国象棋 - 摆上马

admin

https://www.luogu.com.cn/problem/P5005


题目背景
相信自己的做法 大喊一声 I won't MLE！您就会过这道题

Imakf玩腻了国际象棋，决定玩一玩中国象棋。

他发现中国象棋的马和国际象棋的马有所不同，他意识到这又可以出一道简单的问题，于是他又准备摆一摆马了

题目描述
Imakf有一个 XX 行 YY 列的棋盘，还有很多完全相同的马（你可以认为有无数个）。现在在棋盘上摆上马（或者不摆），求任何马无法攻击另一匹马的方案总数。

中国象棋的马和国际象棋的马不同。



注意：实际问题中是没有兵的。

当然由于方案可能过多，请输出对(10^9+7)(10
9
+7)取模的值

输入格式
第一行两个正整数 X,YX,Y。

输出格式
方案对 (10^9+7)(10
9
+7) 取模的值。

输入输出样例
输入 #1复制
1 1
输出 #1复制
2
输入 #2复制
3 3
输出 #2复制
145
说明/提示
对于 100% 的数据，有X\leq100,Y\leq6X≤100,Y≤6

对于 20% 的数据，有X,Y\leq6X,Y≤6

对于另外 20% 的数据，有X\leq20X≤20

对于样例1，可以选择不摆或者摆

对于样例2，我有一个绝妙的解释可惜我写不下。