题目描述

Nikola 小朋友最近在学乘法口诀。为了记得更牢，他决定做一个游戏进行练习。

他画了一个 $r$ 行 $s$ 列的矩阵，每个格子里都有一个正整数。他想知道，如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 $n$ 的路径有多少条？

由于答案可能很大，所以请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行三个正整数 $r,s,n$。

接下来 $r$ 行，每行 $s$ 个正整数，依次表示矩阵每一行的数。

输出格式

输出一行一个整数表示答案。

2 3 200
2 3 4
5 6 7

2

共有 $3$ 条路径，其中有 $2$ 条满足条件：

• $2 \rightarrow 3 \rightarrow 6 \rightarrow 7$，乘积为 $252$；
• $2 \rightarrow 5 \rightarrow 6 \rightarrow 7$，乘积为 $420$。

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

3

数据范围/提示

对于 $20\%$ 的数据：矩阵中的数不超过 $10$。

对于 $50\%$ 的数据：$1\le r,s \le 100$。

对于 $100\%$ 的数据：$1\le r,s \le 300$，$1\le n \le 10^6$，矩阵中的数不超过 $10^6$。