题意概述

给定一个 $r \times s$ 的矩阵，每个格子有一个正整数。
从左上角 $(1,1)$ 走到右下角 $(r,s)$，每次只能向右或向下走。
定义一条路径的权值为路径上所有格子数值的乘积。
求权值不小于 $n$ 的路径条数，答案对 $10^9+7$ 取模。

数据范围：$r,s \le 300$，$n \le 10^6$，矩阵元素 $\le 10^6$。

---

核心难点

1. 路径数：从 $(1,1)$ 到 $(r,s)$ 的路径总数是 $\binom{r+s-2}{r-1}$，最大约 $10^{90}$ 量级，无法直接枚举。
2. 乘积增长：路径乘积可以极大（$300$ 个数乘积可能达到 $(10^6)^{300} = 10^{1800}$），无法直接存储。
3. 约束：要求乘积 $\ge n$，不是模意义下的比较，而是真实数值比较。

---

关键观察

由于 $n \le 10^6$，我们可以将“乘积不小于 $n$”转化为：
设路径乘积为 $P$，如果 $P \ge n$，则 $\lfloor \frac{n-1}{P} \rfloor = 0$，否则 $\ge 1$。
但这并不利于直接 DP。

更直接的想法：
乘积 $P$ 可以写成 $k \times q$ 形式，其中 $k = \gcd(P, n)$ 等，但更常用技巧是：

---

转化为对数比较

取对数：$\log P = \sum \log a_{i,j}$。
条件 $P \ge n$ 等价于 $\log P \ge \log n$。

由于 $a_{i,j} \le 10^6$，$\log a_{i,j} \le \log 10^6 \approx 13.8$，路径最多 $600$ 步，$\log P \le 8280$，可用浮点数或定点数存储。
但浮点数有精度问题，可能影响比较。

---

更稳健的方法：质因数分解

因为 $n \le 10^6$，可以将其质因数分解。
设 $n = p_1^{e_1} p_2^{e_2} \dots p_m^{e_m}$。
对于路径乘积 $P$，要满足 $P \ge n$，等价于：
对每个质因子 $p$，$P$ 中 $p$ 的指数不小于 $n$ 中 $p$ 的指数。

不对！ 因为即使每个质因子的指数都达到要求，$P$ 还可能比 $n$ 小（比如其他质因子指数为0，但 $n$ 有其他因子？实际上 $P$ 包含所有 $n$ 的质因子且指数足够时，$P$ 一定是 $n$ 的倍数，所以 $P \ge n$ 成立）。
更准确：$P \ge n$ 等价于 $P$ 是 $n$ 的倍数，且 $P/n \ge 1$，但 $P/n$ 可能不是整数？不，若 $P$ 是 $n$ 的倍数，则 $P/n \ge 1$ 自动成立。

因此等价条件是：
$P$ 是 $n$ 的倍数。

因为如果 $P$ 是 $n$ 的倍数，则 $P \ge n$（因为矩阵元素是正整数）。
反过来，如果 $P \ge n$，不一定 $P$ 是 $n$ 的倍数。
所以这个转化是错的，不能直接等价。

---

正确转化：阈值法

设 $n$ 的质因数分解为 $n = \prod p_i^{e_i}$。
对于 $P$，设它在 $p_i$ 上的指数为 $f_i$，则： [ P \ge n \iff \prod p_i^{\max(0, f_i - e_i)} \times \text{(其他质因子幂)} \ge 1 ] 这并不好直接处理。

常用技巧：
令 $T = n-1$，那么 $P \ge n$ 等价于 $\lfloor T/P \rfloor = 0$。
但 $P$ 可能很大，不能直接除。

---

动态规划状态设计

设 $dp[i][j][v]$ 表示走到 $(i,j)$ 时，路径乘积为 $v$ 的路径数。
但 $v$ 可能极大，不能直接存。

注意到我们只关心 $v$ 是否 $\ge n$，以及 $v$ 和 $n$ 的比值在某种意义下的状态。
因为 $n \le 10^6$，我们可以考虑存储 $v$ 模 $n$ 的值？不行，模 $n$ 不能判断大小。

另一个思路：
令 $g = \gcd(v, n)$，并存储 $v/g$ 的某些信息？
设 $v = g \times t$，其中 $g \mid n$，且 $\gcd(t, n) = 1$。
那么 $v \ge n$ 等价于 $t \ge n/g$。

---

关键突破：状态为 (i, j, k)

定义 $k = \lfloor \frac{n-1}{v} \rfloor$。
这里 $v$ 是路径乘积。
$k$ 的范围是 $0$ 到 $n-1$。
当 $v \ge n$ 时，$k = 0$；否则 $k \ge 1$。

转移时，从 $(i,j)$ 到 $(i+1,j)$ 或 $(i,j+1)$，$v$ 乘以 $a_{i,j}$，对应 $k$ 变为 $\lfloor \frac{n-1}{v \times a} \rfloor$。
这个转移可以写为： [ k' = \left\lfloor \frac{k}{a} \right\rfloor \quad \text{? 验证:} ] 因为 $k = \lfloor \frac{n-1}{v} \rfloor$，所以 [ k' = \left\lfloor \frac{n-1}{v \cdot a} \right\rfloor = \left\lfloor \frac{\lfloor \frac{n-1}{v} \rfloor}{a} \right\rfloor ] 这是正确的吗？
有公式 $\lfloor \frac{\lfloor x \rfloor}{a} \rfloor = \lfloor \frac{x}{a} \rfloor$ 当 $a$ 是正整数时成立。
因此： [ k' = \left\lfloor \frac{k}{a} \right\rfloor ] 成立。

因此，我们只需要 DP 状态 $(i,j,k)$，其中 $k = \lfloor \frac{n-1}{v} \rfloor$，$v$ 是当前乘积。
初态：$(1,1, \lfloor \frac{n-1}{a_{1,1}} \rfloor)$。
终态：$(r,s,0)$ 的路径数即为所求（因为 $k=0$ 时 $v \ge n$）。

---

DP 转移

设 $dp[i][j][k]$ 表示走到 $(i,j)$ 时 $k = \lfloor \frac{n-1}{v} \rfloor$ 的路径数。
转移： [ dp[i+1][j][\lfloor k/a_{i+1,j} \rfloor] \ += dp[i][j][k] ] [ dp[i][j+1][\lfloor k/a_{i,j+1} \rfloor] \ += dp[i][j][k] ] 所有运算在模 $10^9+7$ 下进行。

---

复杂度

状态数：$r \times s \times n$，最大 $300 \times 300 \times 10^6$，显然太大。
需要优化。

注意 $k$ 的取值：
初始 $k \le n-1$，每次转移 $k$ 变为 $\lfloor k/a \rfloor$，$a$ 是矩阵元素。
因为 $a \ge 1$，$k$ 会快速减小。
实际上，$k$ 的不同取值个数是 $O(\sqrt{n})$ 级别？
更准确：经过多次除以 $a$（$a \ge 2$），$k$ 很快到 0。
但最坏情况 $a=1$ 时 $k$ 不变。
所以当 $a=1$ 时，$k$ 不变，状态可能很多。

---

优化：只存有效状态

用 map 或 unordered_map 存储每个 $(i,j)$ 对应的 $k$ 的分布。
由于 $k$ 取值是整数除法下递降的，不同 $k$ 的数量是 $O(\sqrt{n})$ 级别（实际上更少，因为每次除以至少 1，且矩阵元素不一定全为 1）。

但 $r,s \le 300$，$n \le 10^6$，最坏情况 $a_{i,j}=1$ 时 $k$ 始终为 $n-1$，这样每个 $(i,j)$ 只有一个 $k$ 值，总状态数 $300\times 300 = 9\times 10^4$，可以接受。
如果 $a$ 较大，$k$ 会迅速减小，状态更少。

所以用 unordered_map 存 $k \to count$ 映射，总状态数可接受。

---

算法步骤

1. 读入 $r,s,n$ 和矩阵 $a$。
2. 初始化：$dp[1][1][ \lfloor (n-1)/a[1][1] \rfloor ] = 1$。
3. 按行、列顺序遍历 $(i,j)$，对每个 $dp[i][j]$ 中的每个 $(k, cnt)$：
   • 向右走：$nk = \lfloor k / a[i][j+1] \rfloor$，$dp[i][j+1][nk] += cnt$。
   • 向下走：$nk = \lfloor k / a[i+1][j] \rfloor$，$dp[i+1][j][nk] += cnt$。
4. 最终答案 = $dp[r][s][0]$。

---

复杂度分析

每个 $(i,j)$ 处 $k$ 的不同取值个数是 $O(\sqrt{n})$ 级别，但实际更小。
总状态数约 $O(rs\sqrt{n})$，最坏 $300\times 300\times 1000 \approx 10^8$，可能稍大，但很多 $k$ 会快速变为 0，实际运行可过。

---

总结

本题核心是将“乘积不小于 $n$”转化为 $\lfloor (n-1)/P \rfloor = 0$，并利用整数除法的性质设计 DP 状态 $k = \lfloor (n-1)/P \rfloor$，转移为 $k' = \lfloor k/a \rfloor$。
通过只存储有效状态，将巨大的乘积范围压缩到 $0 \sim n-1$ 的整数，实现了可行解法。
复杂度 $O(rs \cdot S)$，其中 $S$ 是 $k$ 的不同取值个数，实际运行较快。