殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，現在要講的是殿壬三歲大的故事。
這天，殿壬牽著他的貓貓來到了 NPSC 魔法學院的魔幻迷宮中。既然是貓貓，當然很喜歡玩躲貓貓囉！因此到了迷宮之後，貓貓就迅速地跑去躲起來了，讓殿壬來找貓貓！
魔幻迷宮可以用一個高度為 N，寬度為 M 的方格圖表示，左上方的座標是 (1,1)，右下方的座標是 (N,M)，其中往下為 +x 方向，往右為 +y 方向。迷宮中有些格子是無法穿越的障礙物，剩下的格子則可以自由通行。
這個迷宮之所以稱作魔幻迷宮，是因為每次迷宮中的一個格子可能會由障礙物變為可以走的空地，或從可以走的空地變成一個不能走的障礙物。此外，在魔幻迷宮中每次移動只能往下、往左或往右，並且走過的格子不能重複經過。
在殿壬找貓貓的過程中，貓貓因為等著等著太無聊了，居然在計算殿壬從起始點出發，找到貓貓的方法數有幾種！
現在，給你過程中迷宮所發生的 Q 個事件。請你依照事件，告訴貓貓殿壬有多少方法可以找到他呢？
輸入第一行有三個整數 N,M,Q，代表迷宮可以用一個 N × M 的方格圖表示，並且在殿壬找貓貓的過程中，魔幻迷宮發生了 Q 個事件。
接下來的 N 行，每行有一個長度為 M 的0/1字串。若第 i 行、第 j 列中的字元為0，代表
(i,j)方格是個空地；若第 i 行、第 j 列的字元為1，代表(i,j)方格有障礙物。
接下來的 Q 行為殿壬找貓貓的過程中，魔幻迷宮所發生的事件，每個事件可以用三個整數來表示，且形式為以下兩種中的一種：
對於每個形式為2 a b的事件，請輸出一行包含一個整數，代表殿壬找到貓貓的方法數除以109 +7的餘數。
2 2 3 00 00 2 1 2 1 1 2 2 1 2
2 1
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||