棋盘
时间限制：10s 空间限制：512MB
题目描述
给出一个N*M的方格棋盘，每个格子里有一盏灯和一个开关，开始的时候，所有的灯都是关着的。用(x, y)表示第x行，y列的格子。(x, y)的开关可以改变(x, y)中灯的状态，同时也可以改变满足|x’-x|=2,|y’-y|=1或者|x’-x|=1,|y’-y|=2的格子(x’, y’)的状态。改变状态的意思是，原来开着的灯会被关掉，原来关着的灯会被开起来。注意这边的改变状态是强制改变的。每个格子的开关最多只能按一次，求能使得所有灯都打开的方案数mod123456789的值。
输入格式
第一行，N,M。
输出格式
输出一个整数，表示答案。
样例输入
2 3
样例输出
4
提示
【样例解释1】
XX. .X. XXX .XX
XX. XXX .X. .XX
其中X代表按这个格子的开关。
【数据规模与约定】
对于100%的数据，N,M<=150。
题目来源
没有写明来源