#3136. 「COCI 2019.3」Mobitel

内存限制:64 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: alpha1022

题目描述

译自 COCI 2018/2019 Contest #6 T5「Mobitel」,感谢北京省选前集训 / 罗剑桥提供翻译。

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

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

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

输入格式

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

输出格式

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

样例

样例输入 1

2 3 200
2 3 4
5 6 7

样例输出 1

2

样例解释 1

共有 3 条路径,其中有 2 条满足条件:

  • 2 \to 3 \to 6 \to 7 ,乘积为 252
  • 2 \to 5 \to 6 \to 7 ,乘积为 420

样例输入 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