|Mr. Purple is a very imaginative and creative person. In his spare time he invents different puzzles and games. Recently he has come up with a new puzzle called "Knights Out". Mr. Purple likes his new idea very much, but he is somewhat afraid that it may appear to be too easy or too hard. Therefore, Mr. Purple would like to know how many solutions these puzzles have before he presents the idea to puzzle-producing companies.
"Knights Out" is a one-player game played on a NxM rectangular board divided into 1x1 squares. Each square on the board can be white or black. Initially all the squares are white.
A knight is a chess piece that moves by simultaneously shifting one square horizontally and two squares vertically, or one square vertically and two squares horizontally. Two squares A and B on the board are called neighboring if it's possible to make a single knight's move to reach B from A.
In one move the player can choose a square on the board and simultaneously change colors of the chosen square and all its neighboring squares (white becomes black and vice versa). The game is finished when all the squares are colored black.
A sequence of moves is called a solution if it transforms the white board into a black one, and there's no cell which is chosen in more than one move. Note that when a cell is chosen, its neighbors which get changed do not also count as being "chosen" in that step. It's not hard to see that the order of moves doesn't matter, so any solution can be viewed as a set of moves. Two solutions are considered distinct if the corresponding sets are distinct. Return the number of distinct solutions modulo 123,456,789.
|-||N and M will each be between 1 and 150, inclusive.|