A5874. 「COCI 2019.3」Mobitel
编程题
省选/NOI-
知识点
题目描述
**译自 [COCI 2018/2019 Contest #6](https://hsin.hr/coci/archive/2018_2019/) T5「[Mobitel](https://hsin.hr/coci/archive/2018_2019/contest6_tasks.pdf)」，感谢北京省选前集训 / 罗剑桥提供翻译。**
Nikola 小朋友最近在学乘法口诀。
为了记得更牢，他决定做一个游戏进行练习。
他画了一个 $r$ 行 $s$ 列的矩阵，每个格子里都有一个正整数。
他想知道，如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 $n$ 的路径有多少条？
由于答案可能很大，所以请输出答案对 $10^9 + 7$ 取模的结果。
Nikola 小朋友最近在学乘法口诀。
为了记得更牢，他决定做一个游戏进行练习。
他画了一个 $r$ 行 $s$ 列的矩阵，每个格子里都有一个正整数。
他想知道，如果从左上角走到右下角，且每次只能向右或向下走到相邻格子，那么使得路径上所有数的乘积不小于 $n$ 的路径有多少条？
由于答案可能很大，所以请输出答案对 $10^9 + 7$ 取模的结果。
输入格式
第一行三个正整数 $r,s,n$。
接下来 $r$ 行，每行 $s$ 个正整数，表示这个矩阵。
接下来 $r$ 行，每行 $s$ 个正整数，表示这个矩阵。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
2 3 200 2 3 4 5 6 7
输出 #1
2
输入 #2
3 3 90 2 1 1 45 1 1 1 1 1
输出 #2
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$。
对于 $50\%$ 的数据，$1 \le r,s \le 100$；
对于 $100\%$ 的数据，$1 \le r,s \le 300,1 \le n \le 10^6$，矩阵中的数不超过 $10^6$。