原題來(lái)自：USACO 2006 Nov. Gold

Farmer John 新買(mǎi)了一塊長(zhǎng)方形的牧場(chǎng)，這塊牧場(chǎng)被劃分成 M 行 N 列 (1≤M≤12;1≤N≤12)，每一格都是一塊正方形的土地。FJ 打算在牧場(chǎng)上的某幾格土地里種上美味的草，供他的奶牛們享用。遺憾的是，有些土地相當(dāng)?shù)呢汃?，不能用?lái)放牧。并且，奶牛們喜歡獨(dú)占一塊草地，于是 FJ 不會(huì)選擇兩塊相鄰的土地，即：沒(méi)有哪兩塊草地有公共邊。當(dāng)然，F(xiàn)J 還沒(méi)有決定在哪些土地上種草。

作為一個(gè)好奇的農(nóng)場(chǎng)主，F(xiàn)J 想知道，如果不考慮草地的總塊數(shù)，那么，一共有多少種種植方案可供他選擇。當(dāng)然，把新的牧場(chǎng)荒廢，不在任何土地上種草，也算一種方案。請(qǐng)你幫 FJ 算一下這個(gè)總方案數(shù)。

第 1 行：兩個(gè)正整數(shù) M 和 N，用空格隔開(kāi)；
第 2 到 M+1 行：每行包含 N 個(gè)用空格隔開(kāi)的整數(shù)，描述了每塊土地的狀態(tài)。輸入的第 i+1 行描述了第 i 行的土地。所有整數(shù)均為 0 或 1，1 表示這塊土地足夠肥沃，0 則表示這塊地上不適合種草。

第 1 行：輸出一個(gè)整數(shù)，即牧場(chǎng)分配總方案數(shù)除以 10⁸  的余數(shù)。

樣例說(shuō)明
按下圖把各塊土地編號(hào)：
1 2 3  
0 4 0
只開(kāi)辟一塊草地有 4 種方案：選 1,2,3,4 中的任一塊。開(kāi)辟兩塊草地的話，有 3 種方案：13,14 以及 34。選三塊草地只有一種方案：134。再加把牧場(chǎng)荒廢的那一種，總方案數(shù)為 4+3+1+1=9 種。
數(shù)據(jù)范圍與提示：1≤N,M≤12。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃