题目描述
小W从农村搬到了城市居住，好不习惯啊，因为农村有广阔的田野可以奔跑，而城市除了房子还有车子，很难嗅到泥土的芬芳。这不，小W好不容易在犄角旮旯处找到一片土地，这块不大的土地被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。小W打算在这片泥土上的某几格里种上美味的玉米，长大了好供他享用。
遗憾的是，有些土地相当贫瘠，不能用来种玉米。并且，小W想营造种植的艺术美，于是小W不会选择两块相邻的土地同时种玉米，也就是说，没有哪两块种植玉米的土地有公共边。
小W想知道，一共有多少种种植方案可供他选择？（当然，把土地完全荒废也是一种方案，也是一种美）
输入
第一行：M和N (1≤M≤12，1≤N≤12) 。
接下来M行，每行N个数，1表示该矩形块可以种玉米，0表示该矩形块是贫瘠的，不能种玉米。
输出
一个整数，即牧场分配总方案数，由于结果可能很大，你需要输出真实方案数除以1000000000的余数。
样例输入输出
提示
【提示】
从上往下，从左到右给可能种玉米的地编上号，为：
1 2 3
0 4 0
种0块，有1种种法；
种1块，有4种种法：(1),(2),(3),(4)；
种2块，有3种种法：(1,3),(1,4),(3,4)；
种3块，有1种种法：(1,3,4)；
共计1+4+3+1=9种种法。
【数据范围】
30%的数据，M=1。
100%的数据，1≤M,N≤12。