#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

HINT

Append Code