小 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 的余数。
2 3 1 1 1 0 1 0
9
【提示】 从上往下，从左到右给可能种玉米的地编上号，为： 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。