Problem Background

Little Nikola is recently learning multiplication tables.
To remember them better, he decides to practice through a game.

Problem Description

He draws a matrix with $r$ rows and $s$ columns, where each cell contains a positive integer.
He wants to know how many paths exist from the top-left corner to the bottom-right corner, where each move can only be to the right or down to an adjacent cell, such that the product of all numbers on the path is not less than $n$.

Since the answer might be very large, output the result modulo $10^9 + 7$.

Input Format

The first line contains three positive integers $r, s, n$.
The next $r$ lines, each containing $s$ positive integers, represent the numbers in the matrix row by row.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2 3 200
2 3 4
5 6 7

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Notes

Sample 1 Explanation:

There are 3 paths in total, of which 2 meet the condition:
$2 \rightarrow 3 \rightarrow 6 \rightarrow 7$, product is $252$
$2 \rightarrow 5 \rightarrow 6 \rightarrow 7$, product is $420$

Data Range:

For 20% of the data:
The numbers in the matrix do not exceed $10$.
For 50% of the data:
$1 \le r, s \le 100$.
For 100% of the data:
$1 \le r, s \le 300$.
$1 \le n \le 10^6$.
The numbers in the matrix do not exceed $10^6$.

见题面 Input 部分

见题面 Output 部分