描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角，出口在右下角。 小明被带到地宫的入口，国王要求他只能向右或向下行走。 走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。 当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。 请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
样例输入
2 2 2 1 2 2 1
样例输出
2
样例输入
2 3 2 1 2 3 2 1 5
样例输出
14
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 const int MS=55; 9 const int mod=1000000007;10 11 int dp[MS][MS][15][15];12 int plat[MS][MS];13 14 int n,m,k;15 16 void input()17 {18 cin>>n>>m>>k;19 for(int i=1;i<=n;i++)20 {21 for(int j=1;j<=m;j++)22 {23 cin>>plat[i][j];24 plat[i][j]++;25 // 注意：题目说了每个格子放一个宝物。26 //所以价格为0并不代表没有宝物。代表的是27 //一文不值的宝物 这里将plat都自加128 }29 }30 }31 32 void solve()33 {34 memset(dp,0,sizeof(dp));35 dp[1][1][1][plat[1][1]]=1;36 dp[1][1][0][0]=1;37 // 物理过程法38 for(int i=1;i<=n;i++)39 {40 for(int j=1;j<=m;j++)41 {42 for(int s=0;s<=k;s++)43 {44 // 不取这个格子的宝物45 for(int t=0;t<=13;t++)46 {47 dp[i][j][s][t]=(dp[i][j][s][t]+dp[i-1][j][s][t])%mod;48 dp[i][j][s][t]=(dp[i][j][s][t]+dp[i][j-1][s][t])%mod;49 }50 // 取这个格子的宝物51 for(int w=0;w