UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3690. 棋盘

统计 下载数据

Description

给出一个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的值。

Input

第一行,N,M。

Output

输出一个整数,表示答案。
 

Sample Input

2 3

Sample Output

4

Hint

【样例解释1】

XX.    .X.    XXX    .XX

XX.    XXX    .X.    .XX

其中X代表按这个格子的开关。

【数据规模与约定】

对于100%的数据,N,M<=150。

Source