俄罗斯方块

题目描述:

小keke同学非常喜欢玩俄罗斯方块(* *)，他最近发现传统的俄罗斯方块很无趣，于是他想到了一个新规则的游戏来考验你。

    游戏是这样的：给定你一个宽度为w的游戏场地，我们设高度为正无穷。现在给你3种俄罗斯方块：

    1 x 2的方块

    2 x 2的方块

    2 x 2的方块去掉一个1 x 1的方块

    如果你明白俄罗斯方块的规则的话，方块在下落过程中是可以随便旋转的。而且是从上往下落，上面的落在下面的上面。

    现在给定你一个高度h，让你求出有多少种游戏的方法，使得最后恰好落满h的高度(最上层是齐平的)。因为这样可以得很多很多分!

输入格式:

两个整数h，w含义如题所述。

输出格式:

一个整数，为能达到要求的游戏方法的总数。

样例输入:

2 2

样例输出:

3

提示:

1<=h，w<=9，注意答案有可能很大( 但用不到高精度 )。

时间限制: 1000ms
空间限制: 256MB

---