Office Patrol Tour Equivalence

A company is planning to build offices on an (N \times M) grid. The grid has horizontal and vertical edges with weight (1). During the day all roads are available, so the cost to travel between any two grid points is the Manhattan distance. At night, however, only exactly (N\times M-1) edges are lit – they form a spanning tree (T) of the grid. In the night scenario the cost to travel between any two offices is the length of the unique path between them in (T).

Every day you conduct a patrol: starting at some office, you visit every office in a chosen subset (S) exactly once (in some order) and return to the starting point. The total distance of the tour is defined as the sum of the shortest distances between consecutive offices (using the daytime graph or the nighttime graph, respectively). You wish to choose the subset (S) so that the minimum route length computed in the daytime equals that computed at night.

Note that for any two offices (u) and (v), the daytime cost is the Manhattan distance (|u-v|_1) while the nighttime cost is (d_T(u,v)), the distance in the spanning tree. Since in any grid we have (d_T(u,v) \ge |u-v|_1), equality holds if and only if there exists a Manhattan shortest path from (u) to (v) along which all edges are lit (i.e. belong to (T)). One may show that if the spanning tree (T) is chosen as follows, then for any two vertices (u=(r_1,c_1)) and (v=(r_2,c_2)) the equality (d_T(u,v)=|u-v|1) holds if and only if at least one of (u) or (v) lies in the first row (row 0).

Specifically, suppose the lit (illuminated) edges (forming (T)) are chosen by connecting every office ((r,c)) with (r>0) to the office directly above it, and for offices in row 0 with (c>0) connect them to the office to their left. Then for any pair (u=(r_1,c_1)) and (v=(r_2,c_2)), the unique path in (T) is obtained by going vertically from (u) up to row 0, then horizontally along row 0, and finally vertically down to (v). Its length is (r_1+r_2+|c_1-c_2|), which equals (|u-v|1) (that is, (|r_1-r_2|+|c_1-c_2|)) if and only if at least one of (r_1) or (r_2) is zero.

Thus, a necessary and sufficient condition for a subset (S) to admit a patrol tour whose total route length in the daytime equals that in the nighttime is that there exists a cyclic order of the points in (S) such that for every consecutive pair ((u,v)), at least one of (u) or (v) lies in row 0. (Recall that when computing the tour cost, the route between two chosen offices (u) and (v) is taken to be the corresponding shortest path in the underlying graph, even if it passes through offices not in (S).)

Your task is to compute, modulo (10^9+7), the number of subsets (S) of grid points (i.e. office locations) that satisfy the above property in each of the following cases:
1. (|S| \ge 2).
2. (|S| = 2).
3. (|S| = 3).

It turns out that with the special structure of (T) the condition is equivalent to requiring that if we let (a) be the number of selected offices in row 0 and (b) the number selected elsewhere then a valid (S) must satisfy (b \le a).

Input and output formats are described below. In particular, note that for the cases of 2 and 3 offices the answers can be written in closed‐form as:
[ \text{answer2} = \binom{M}{2} + M\cdot((N-1)\cdot M),\quad \text{answer3} = \binom{M}{3} + \binom{M}{2}\cdot((N-1)\cdot M). ]
For the general case (|S|\ge2), one way to express the answer is
[ \text{answer1} = \sum{a=0}^{M} \binom{M}{a},\left(\sum{b=0}^{a} \binom{(N-1)\cdot M}{b}\right) - \left(1+\binom{M}{1}\right), ]
where the subtraction removes the cases (|S|=0) and (|S|=1).

inputFormat

The input consists of a single line containing two integers (N) and (M) (with (N, M \ge 1)). (N) is the number of rows and (M) is the number of columns in the grid.

outputFormat

Output three space‐separated integers: the number of valid subsets (S) with (|S| \ge 2), with (|S| = 2) and with (|S| = 3), respectively, modulo (10^9+7).

sample

2 2

8 5 2