Description

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$.

Input Format

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 Format

Output one line with one integer representing the answer.

2 3 200
2 3 4
5 6 7

2

3 3 90
2 1 1
45 1 1
1 1 1

3

Hint

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