1483 . 電腦檢查
TopCoder
Tags
Description
你是一名盡責的電腦老師。
每當放學時，你總要檢查教室裡的電腦是否有被學生破壞（拔線、灌H-Game(Heuristic Game)之類的）
電腦教室裡面總共有 R x C 台電腦（擺成 R 列每列 C 台）。
但是因為你很懶惰，所以你只會檢查在你回家動線上的電腦（不一定動線上的電腦全都要檢查）
（你的辦公桌在教室的最左前方，而唯一的出口則在教室的最右後方）
另外，為了節省檢查的時間，你決定參考每個學生的『糟糕度』（做壞事的機率）來決定檢查與否
當你檢查一個學生的電腦沒問題時，你覺得『糟糕度』在他以下（包括相等）的學生都不會有問題了，所以你之後就絕對不會檢查那些人的電腦。
因為你是個『盡責』的老師，所以你至少要檢查一台電腦，才不會被說閒話。
現在你想要知道，你總共有幾種方式檢查教室的電腦。
Input Format
本題有多筆測試資料：
第一行有一個數字 T，代表接下來有 T 筆測試資料
每筆測試資料的：
第一行有兩個數字 R,C，代表教室共有 R x C 台電腦（擺成 R 列每列 C 台）。
接下來有 R 行，每行有 C 個數字，分別代表每個學生的『糟糕度』
所有數字都不會超過1000。
Output Format
對於每筆測試資料輸出一個數字 k ，代表共有 k 種方式檢查電腦（因為 k 可能很大，所以請輸出 k 除以 1,000,000,007 的餘數）
Sample Input 1
2
2 2
1 2
3 4
2 1
2
1
2 2
1 2
3 4
2 1
2
1
Sample Output 1
11
2
2
Hints
第一組測試資料共有下列11種走法：
1, 2, 3, 4, 12, 13, 14, 24, 34, 124 以及 134.
第二組測試資料共有下列2種走法：
2, 1
Problem Source
原TIOJ1483 / 建中校內培訓第六次模擬考試。
Problem Setter：hallogameboy、peter50216
(Adapt From:TCPC'08)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |