P8612 [Lanqiao Cup 2014 NOI Qualifier AB] Underground Palace Treasure Hunt

The king of Country X has an underground palace treasure vault. It is a matrix of $n \times m$ cells. Each cell contains one treasure. Each treasure has a value tag. The entrance of the underground palace is at the top-left corner, and the exit is at the bottom-right corner. Xiaoming is brought to the entrance, and the king requires that he may only move right or down. When passing through a cell, if the treasure value in that cell is greater than the value of any treasure currently in Xiaoming’s hand, Xiaoming may pick it up (of course, he may also choose not to). When Xiaoming reaches the exit, if he has exactly $k$ treasures in his hand, then these treasures will be given to him. Please help Xiaoming compute: under the given situation, how many different action plans allow him to obtain these $k$ treasures.

The first line contains $3$ integers separated by spaces: $n$, $m$, $k(1 \le n,m \le 50,1 \le k \le 12)$. Then follow $n$ lines of data. Each line contains $m$ integers $C_i(0 \le C_i \le 12)$, representing the value of the treasure in that cell.

Output one integer, representing the number of action plans that pick exactly $k$ treasures. This number may be very large; output it modulo $1000000007(10^9+7)$.

Time limit: 1 second, 256M. The 5th Lanqiao Cup Provincial Contest in 2014. Translated by ChatGPT 5