U531853 TopCoder SRM494 Div1 KnightsOut

[原题链接(无法提交)](https://archive.topcoder.com/ProblemStatement/pm/8744)

给出一个 $n∗m$ 的方格棋盘，每个格子里有一盏灯和一个开关，开始的时候，所有的灯都是关着的。 用 $(x,y)$ 表示第 $x$ 行，$y$ 列的格子。 $(x,y)$ 的开关可以改变 $(x,y)$ 中灯的状态，同时也可以改变满足 $|x′−x|=2,|y′−y|=1$ 或者 $|x′−x|=1,|y′−y|=2$ 的格子 $(x′,y′)$ 的状态。 改变状态的意思是，原来开着的灯会被关掉，原来关着的灯会被开起来。注意这边的改变状态是强制改变的。每个格子的开关最多只能按一次，求能使得所有灯都打开的方案数 $\mod 123456789$ 的值。

共一行，两个正整数 $n,m$。 $1\le n,m\le600$。

共一行，一个整数表示方案数模 $123456789$ 后的值。