{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cp\u003e 农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。\u003c/p\u003e \n \u003cp\u003e 遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。\u003c/p\u003e \n \u003cp\u003e John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)\u003c/p\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cp\u003e \u003cspan\u003e第一行:两个整数M和N,用空格隔开。\u003c/span\u003e\u003c/p\u003e \n \u003cp\u003e \u003cspan\u003e第2到第M\u003c/span\u003e+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。第i+1行描述了第i行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。\u003c/p\u003e \n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e一个整数,即牧场分配总方案数除以100\u003c/span\u003e,000,\u003cspan\u003e000的余数。\u003c/span\u003e\u003c/span\u003e\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n2 3\r\n1 1 1\r\n0 1 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n9\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv\u003e\n Number the squares as follows:\n \u003cbr\u003e \n \u003cpre\u003e\r\n\t1 2 3\r\n\u0026nbsp; 4 \u0026nbsp;\u003c/pre\u003e \n \u003cbr\u003e There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1\u003d9.\n\u003c/div\u003e"}}]}