P5307 [COCI 2018/2019 #6] Mobitel

The child `Nikola` has recently been learning the multiplication table. To remember it better, he decided to make a game to practice.

He drew a matrix with $r$ rows and $s$ columns, and each cell contains a positive integer. He wants to know: if you walk from the top-left corner to the bottom-right corner, and each step can only go right or down to an adjacent cell, how many paths have the product of all numbers on the path not less than $n$? Since the answer may be very large, output the result modulo $10^9 + 7$.

The first line contains three positive integers $r, s, n$. Next come $r$ lines, each containing $s$ positive integers, representing the numbers in each row of the matrix in order.

Output one line with one integer representing the answer.

### Sample $1$ Explanation: There are $3$ paths in total, among which $2$ satisfy the condition: $2 \rightarrow 3 \rightarrow 6 \rightarrow 7$, with product $252$. $2 \rightarrow 5 \rightarrow 6 \rightarrow 7$, with product $420$. ### Constraints: For $20\%$ of the testdata: The numbers in the matrix do not exceed $10$. For $50\%$ of the testdata: $1 \le r, s \le 100$. For $100\%$ of the testdata: $1 \le r, s \le 300$. $1 \le n \le 10^6$. The numbers in the matrix do not exceed $10^6$. Translated by ChatGPT 5