TopCoder

User's AC Ratio

100.0% (39/39)

Submission's AC Ratio

53.0% (141/266)

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

Sample Output 1

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11