3632: 生日礼物
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
今天是 1 月 22 号，是 Y 的生日。
为了准备生日礼物， π + e 绞尽脑汁，把他在数字电路课堂上用的面包板改
造了一下，变成了一块 n × m 大小的 LED 屏幕。
为了给 Y 制造惊喜， π + e 在每个发光二极管后面都装了一个小开关，一旦
改变位置 (x0, y0) 的开关状态，那么在 LED 屏幕上，像素点 (x0, y0) 以及满足
|x − x0| = 1、 |y − y0| = 2 或者 |x − x0| = 2、 |y − y0| = 1 的像素点的状态也会发
生改变（亮变暗、暗变亮）。
现在， π + e 要在 Y 面前，把他亲手制作的 LED 板由全暗的状态全部点亮。
同时为了展现自己高超的智商，他还要说出总共有多少种方法能够完全点亮这 块 LED。 由于一个开关按两次相当于没按，因此限定每个位置的开关最多只能按一 次。
“不是很懂理工男的浪漫。”
输入
输入一行，两个正整数 n, m，表示 LED 屏幕的大小。其中 1 ≤ n, m ≤ 600。
输出
输出一行，一个整数 S，表示将全暗变成全亮的操作方案数。输出结果请对
123456789 取模。
样例输入 复制
2 3样例输出 复制
4提示
【样例输入 2】
3 3
【样例输出 2】
1
【样例解释】
可以证明，只有将 9 个开关全部按一遍，才能点亮所有 LED 灯。
【数据规模与约定】 对于 20% 的数据，有 1 ≤ n × m ≤ 20；
对于 40% 的数据，有 1 ≤ n × m ≤ 200； 对于 70% 的数据，有 1 ≤ n, m ≤ 150；
对于 100% 的数据，有 1 ≤ n, m ≤ 600。