F. Random Maze
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a grid of $$$N \times M$$$ square cells, with height $$$N$$$ units and width $$$M$$$ units. The outer border of the grid is a wall. There are 2 holes in the wall: to access the entrance (top left) cell and the exit (bottom right) cell.

The internal part of the grid consists of $$$L=2\cdot N \cdot M-(N+M)$$$ internal segments of unit length. You have $$$K$$$ walls of unit length, and you must place each of those walls at one of the internal segments (you can't place two or more walls at the same segment).

For example, the picture below shows a grid with $$$N=3$$$ and $$$M=5$$$. There are $$$L=22$$$ internal segments and there are $$$K=6$$$ walls placed.

You place walls randomly. That is, you take a wall, pick one of the free internal segments with equal probability, and place the wall there. You repeat this procedure until you have placed all $$$K$$$ walls. Let's call the result a random maze with $$$K$$$ walls.

After this, you check if the maze is solvable. The maze is solvable if there is a path from the top left cell to the bottom right cell. Formally, the maze is solvable if there exists a sequence of cells, such that the first cell in the sequence is the top left cell, the last cell in the sequence is the bottom right cell, and for every two cells adjacent in the sequence, they are adjacent by side in the grid, and there is no wall placed between them.

For every integer $$$K \in [0, L]$$$, compute the probability that a random maze with $$$K$$$ walls is solvable.

Input

Two numbers $$$N,M$$$ — size of the grid. $$$1 \le N \le 7$$$. $$$ 1 \le M \le 100$$$. $$$N \cdot M \le 100$$$.

Output

Print $$$L+1$$$ integers $$$p'_0, p'_1, \dots p'_L$$$ on a single line. $$$p'_K$$$ is the probability that a random maze with $$$K$$$ walls is solvable, modulo $$$10^9+7$$$.

Formally, it can be shown that the probability for a given $$$K$$$ can be expressed as an irreducible fraction $$$p_K=\frac{a_K}{b_K}$$$, where $$$a_K$$$ and $$$b_K$$$ are integers and $$$b_K \not \equiv 0 ~(\text{mod} ~ 10^9+7)$$$. For every $$$K \in [0, L]$$$, output the integer $$$p'_K = a_K \cdot b_K^{-1} ~(\text{mod} ~ 10^9+7)$$$. In other words, output such an integer $$$p'_K$$$ that $$$0 \le p'_K \lt 10^9+7$$$ and $$$p'_K \cdot b_k \equiv a_k ~(\text{mod} ~ 10^9+7)$$$.

Examples
Input
2 2
Output
1 1 333333336 0 0
Input
1 4
Output
1 0 0 0
Input
3 2
Output
1 1 809523816 542857147 885714292 0 0 0
Note

In the first test:

  • For $$$K=0$$$ or $$$K=1$$$, any maze is solvable.
  • For $$$K=3$$$ or $$$K=4$$$, any maze is not solvable (so the probability of it being solvable is 0).
  • For $$$K=2$$$, there are in total 6 different mazes, all possible with equal probability $$$\frac{1}{6}$$$. 2 of them are solvable (see picture below). So, the probability of a random maze being solvable is $$$\frac{2}{6}=\frac{1}{3}$$$.

In the second test $$$N=1$$$, so if there is at least one wall placed, it always blocks the path from start to end, so the probability of the maze being solvable is 0 for all $$$K \ge 1$$$.