题目描述

FJ 的农场里有一个存放着各种宝贝的地窖。地窖呈矩形，有 \(n×m\) 个房间，每个房间一个宝贝，每个宝贝都有自己的价格。入口在地窖的左上角，出口在地窖的右下角，FJ 带奶牛贝蒂来到地窖的入口后告诉贝蒂，贝蒂每次只能向右或者向下走，每走进一个房间，如果当前这个房间的宝贝价格比她手中任意一个宝贝的价格都要高，那么她可以取走这个房间的宝贝（当然她也可以不拿）。

那么现在请你帮贝蒂计算一下，贝蒂有多少种行走方案可以使得她到达出口时手上的宝贝数正好是 \(k\)。

格式

输入格式

输入第 \(1\) 行 \(3\) 个整数，用空格分开：\(n,m,k (1<=n,m<=50,1<=k<=12)\)；

接下来是一个 \(n×m\) 的矩阵，每个位置的数字 \(C_i (0<=C_i<=12)\) 表示该房间宝贝的价格。

输出格式

输出 \(1\) 个整数，表示正好取 \(k\) 个宝贝的行动方案数。该数字可能很大，输出它对 \(1000000007\) 取模的结果。

样例1

输入样例1

2 2 2
1 2
2 1

输出样例1

2

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)