← 返回题目
题库练习 「COCI 2019.3」Mobitel
← 上一题 下一题 →

A5874 | 「COCI 2019.3」Mobitel

时间限制6s
内存限制64MB
通过 / 提交0/0

题目描述

**译自 [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$ 取模的结果。

输入格式

第一行三个正整数 $r,s,n$。
接下来 $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
C++ 编辑器
输入
输出