TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

43.8% (21/48)

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

2
2 2
1 2
3 4
2 1
2
1

Sample Output

11
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

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 65536
1 3000 65536 65536
2 3000 65536 65536
3 3000 65536 65536
4 3000 65536 65536
5 3000 65536 65536
6 3000 65536 65536
7 3000 65536 65536
8 3000 65536 65536
9 3000 65536 65536
10 3000 65536 65536