Counting Valid Paths in a Matrix

You are given an r x s matrix, where every cell contains a positive integer. You need to count the number of paths from the top‐left cell to the bottom‐right cell such that the product of all the numbers along the path is at least \(n\). In each step, you can move either to the right or down to an adjacent cell.

Since the answer can be very large, output the result modulo \(10^9+7\).

Note: The input guarantees that \(r\) and \(s\) are small enough (for example, \(r, s \leq 10\)) so that a simple DFS or recursion over all paths is feasible.

inputFormat

The first line contains three space-separated integers \(r\), \(s\), and \(n\) where:

• \(r\) is the number of rows.
• \(s\) is the number of columns.
• \(n\) is the minimum required product threshold.

The next \(r\) lines each contain \(s\) space-separated positive integers representing the matrix.

outputFormat

Output a single integer representing the number of valid paths modulo \(10^9+7\).

sample

2 2 10
2 3
4 5

2