Mario is Lost

0

0 votes
Medium
Problem

Mario is living peacefully in Mushroom World. In spite of having stayed there all his life, there are still some parts of his world which are left undiscovered. In his bid to completely explore his motherland, Mario leaves on a trip. He comes across a piece of land with a number of stones. The land can be assumed to be a rectangle with n rows and m columns with at least one cell without a stone.

Blooper, Mario’s enemy decides to make him lose his way. But being a villain with principles, he follows certain rules. He rearranges the stones on the piece of land such that there is at least one cell without a stone(called clear cell) and all such clear cells are connected i.e. you can move from one clear cell to all other clear cells (if you move from one cell to any side-adjacent cell). Also, the minimum distance from a clear cell (x1,y1) to another (x2,y2) by moving only through clear cells is |x1-x2|+|y1-y2|. If while travelling Mario sees an arrangement of stones he has already seen before, he will know that he is on the wrong path. But Blooper doesn’t want this.

Help Blooper find out the total number of ways he can arrange the stones such that Mario comes across a different arrangement each time and doesn’t know that he is lost. There are plenty of stones available to include in the arrangements, stones can be thrown away too. Since the number of ways can be large, find it modulo 1000000007 (109+7).

Input

The only line contains n,m size of the piece of land

Output

Print the number of ways modulo 109+7

Constraints

1 <= n,m <= 150

Sample Input
2 2
Sample Output
13
Time Limit: 3
Memory Limit: 256
Source Limit:
Editor Image

?