BlackBoxDiv1

Cat Upper has a rectangular black box. On the bottom of the box there is a grid that divides the box into identical square cells. There are N rows of cells, each containing M cells. There are no walls between the cells. The sides of the box are transparent.

Each cell contains a single mirror. Seen from above, the mirror is a segment that connects two opposite corners of the cell. The mirror surface is on both sides of the segment. (Note that for each cell there are two possible positions of the mirror.)

Cat Upper has a laser which can be used to cast rays. When casting a ray, the following rules must be obeyed:

• The ray must be cast from outside of the black box.
• The ray must enter the box exactly in the middle of a side of a cell.
• The ray must enter the box in the direction perpendicular to the side of the box it enters through.

Once inside the box, the laser follows the laws of reflection: it travels in a straight line through open space, and it reflects whenever it hits a mirror. (Note that this means that the laser will always travel in a direction parallel to one of the sides of the box.)

The process ends when the ray exits the black box. (Note that this always has to happen, and that the ray will necessarily leave through the middle of some other cell wall.)

Cat Upper used the laser to cast a ray through each of the 2N+2M cell sides that were visible from the outside. For each cell side C, Upper recorded where the laser that entered through C exited the black box.

Afterwards, Upper removed a single mirror from the grid and repeated the entire experiment. Surprisingly, the results were completely identical to the first experiment.

Cat Upper has lost the black box and he does not remember the cell from which he removed the mirror. The only thing he remembers are the dimensions of the black box.

You are given the two ints N and M. Return the number of possible initial states of the black box, modulo 1,000,000,007.