#OJ1553. I)
I)
I)
Time Limit: 3 Sec Memory Limit: 256 MB
Description
猴哥依旧想继续扩展他的跳格子游戏,还是在一个n*m矩阵中进行游戏。这次他在每个格子里都放了一个物品,每个物品的价值为C (1 <= C <= 12),这次他跳格子的规则如下: 1.他从矩阵的左上角出发,要跳到格子的右下角。 2.他每次只能向下或向右跳一格。 3.当他访问一个格子,这个格子中物品的价值比他手中已有物品的价值都大,他才可以捡起这个物品,当然他可以选择不捡。 猴哥有很多种方案跳到右下角,请你计算当猴哥结束游戏时,他手中有k个物品的方案数x。
Input
第一行输入一个T 代表有T组样例 对于每组样例,第一行输入三个数n,m,k(1 <= n,m <= 50, 0 <= k <= 12)。接下来有n行每行m个数,代表每个格子中物品的价值。
Output
对于每组样例,输出样例编号及满足条件的方案数x(x对1000000007取模)
Sample Input
2
2 2 2
1 2
2 1
2 3 2
1 2 3
2 1 5
Sample Output
Case 1: 2
Case 2: 14