#P5005. 中国象棋 - 摆上马

中国象棋 - 摆上马

题目背景

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

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

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

题目描述

Imakf 有一个 XXYY 列的棋盘,还有很多完全相同的马(你可以认为有无数个)。现在在棋盘上摆上马(或者不摆),求任何马无法攻击另一匹马的方案总数。

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

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

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

输入格式

第一行两个正整数 X,YX,Y

输出格式

方案对 (109+7)(10^9+7) 取模的值。

1 1 

2
3 3 

145

提示

对于 100% 的数据,有 1X1001\le X\leq1001Y61\le Y\leq6

对于 20% 的数据,有 X,Y6X,Y\leq6

对于另外 20% 的数据,有 X20X\leq20

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

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