X 国王有一个地宫宝库，是 n×mn×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 kk 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 kk 件宝贝。

输入格式

第一行 33 个整数，n,m,kn,m,k，含义见题目描述。

接下来 nn 行，每行有 mm 个整数 CiC_i 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 kk 个宝贝的行动方案数。

该数字可能很大，输出它对 10000000071000000007 取模的结果。

数据范围

1≤n,m≤501≤n,m≤50,
1≤k≤121≤k≤12,
0≤Ci≤120≤C_i≤12.

输入样例1：

1
2
3
2 2 2
1 2
2 1

输出样例1：

1
2

输入样例2：

1
2
3
2 3 2
1 2 3
2 1 5

输出样例2：

1
14

思路

题目要求在格子上只能向下和向右走，很明显是要用DP解题，重点是如何设置状态。

当前所处的位置 (i,j)(i,j)，必然是需要记录的状态；为考察最后走到 (n,m)(n,m) 后拿到 kk 个物品的方案数，当前拿到的物品数 cc 也是状态之一；取的物品的价值（我们用 val(i,j)val(i,j) 表示位置 (i,j)(i,j) 物品的价值）需要严格递增，因此我们需要记录已经取的物品的最大价值。设 f(i,j,c,v)f(i,j,c,v) 表示走到位置 (i,j)(i,j)，取了 cc 个物品且最大价值为 vv 的方案数。

考虑取或不取 (i,j)(i,j) 的物品：若取，则取完后最大物品的价值必须为 val(i,j)val(i,j)，前面 c−1c-1 个物品的最大价值在 [0,val(i,j))[0,val(i,j)) 的整数区间内（若 val(i,j)=0val(i,j)=0 需要特判），f(i,j,c,val(i,j))=∑v=0val(i,j)−1[f(i−1,j,c−1,v)+f(i,j−1,c−1,v)]f(i,j,c,val(i,j))=\sum\limits_{v=0}^{val(i,j)-1}[f(i-1,j,c-1,v)+f(i,j-1,c-1,v)]；若不取，则 f(i,j,c,v)=f(i−1,j,c,v)+f(i,j−1,c,v)f(i,j,c,v)=f(i-1,j,c,v)+f(i,j-1,c,v)。

现在考虑边界条件，若一直什么都不取，则 f(i,j,0,0)=(i+j−2i−1)f(i,j,0,0)=\binom{i+j-2}{i-1}，即从 (1,1)(1,1) 走到 (i,j)(i,j) 的方案数；若 val(i,j)=0val(i,j)=0，有特判 f(i,j,1,0)=(i+j−2i−1)f(i,j,1,0)=\binom{i+j-2}{i-1}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: AcWing 1212
Date: 2021 Apr. 5th
Description: Dynamic Programming
*******************************************************************/
#include<iostream>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
ll f[51][51][202][15];
ll val[101][101];
int k, n, m;
ll C[101][101];
void initC() {
	C[0][0] = 1;
	for (int i = 1; i <= 100; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= 100; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
}
int main() {
	initC();
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> val[i][j];
		}
	}
	f[1][1][1][val[1][1]] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//什么都不拿
			f[i][j][0][0] = C[i + j - 2][i - 1];
			if (i == j && j == 1) {
				continue;
			}
			if (val[i][j] == 0) {
				//特判 前面什么都不拿 只拿(i,j)
				f[i][j][1][0] = C[i + j - 2][i - 1];
			}
			for (int c = 1; c <= i + j - 1; c++) {
				for (int v = 0; v <= 12; v++) {
					if (val[i][j] > v) {
						//拿(i,j)
						f[i][j][c][val[i][j]] += (f[i - 1][j][c - 1][v] + f[i][j - 1][c - 1][v]) % MOD;
						f[i][j][c][val[i][j]] %= MOD;
					}
					//不拿(i,j) v可能与val[i][j]重复，这里用+=
					f[i][j][c][v] += (f[i - 1][j][c][v] + f[i][j - 1][c][v]) % MOD;
				}
			}
		}
	}
	//统计取到k个物品的所有情况
	ll ans = 0;
	for (int v = 0; v <= 12; v++) {
		ans += f[n][m][k][v];
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}