2223 - [COCI 2018-2019 #6] Mobitel

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

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

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

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

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

【样例一解释】

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

2 \rightarrow 3 \rightarrow 6 \rightarrow 7，乘积为 252。

2 \rightarrow 5 \rightarrow 6 \rightarrow 7，乘积为 420。

【数据范围】

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

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

对于 100\% 的数据，1\le r,s \le 300,1\le n \le 10^6。

矩阵中的数不超过 10^6。