CF2120D.Matrix game

Aryan 和 Harshith 玩一个游戏。他们都从三个整数 $a$、$b$ 和 $k$ 开始。然后 Aryan 给 Harshith 两个整数 $n$ 和 $m$。接着，Harshith 给 Aryan 一个 $n$ 行 $m$ 列的矩阵 $X$，其中 $X$ 的每个元素都在 $1$ 到 $k$（包含 $k$）之间。之后，如果 Aryan 能在 $X$ 中找到一个 $a$ 行 $b$ 列的子矩阵 $Y$，且 $Y$ 的所有元素都相等，则 Aryan 获胜。

例如，当 $a=2$，$b=2$，$k=6$，$n=3$ 且 $m=3$ 时，如果 Harshith 给 Aryan 如下矩阵，则 Aryan 获胜，因为其中存在一个所有元素都为 $1$ 的 $2\times 2$ 子矩阵，如下所示。

Aryan 给你 $a$、$b$ 和 $k$ 的值。他让你帮他找到字典序最小的二元组 $(n, m)$，使得无论 Harshith 如何选择矩阵 $X$，Aryan 都能获胜。请帮助 Aryan 赢得游戏。假设 Harshith 总是最优地选择矩阵。$n$ 和 $m$ 的值可能很大，请输出它们对 $10^9+7$ 取模后的结果。

一个二元组 $(n_1, m_1)$ 被认为比 $(n_2, m_2)$ 字典序更小，当且仅当 $n_1 < n_2$，或者 $n_1 = n_2$ 且 $m_1 < m_2$。

$^*$ 矩阵的子矩阵是通过从原矩阵中去除若干行和/或列得到的。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每组测试用例包含一行，包含三个用空格分隔的整数 $a, b$ 和 $k$（$1\leq a, b, k \leq 10^5$）。

保证所有测试用例中 $\max(a, b, k)$ 的总和不超过 $10^5$。

对于每组测试用例，输出一行，包含两个用空格分隔的整数 $n$ 和 $m$，表示问题的答案。$n$ 和 $m$ 的值可能很大，请输出它们对 $10^9+7$ 取模后的结果。

对于第一个测试用例，任意 $n\times m$ 的矩阵都包含一个 $1\times 1$ 的所有元素相等的子矩阵。$(1,1)$ 是所有可能二元组中字典序最小的。

对于第二个测试用例，可以验证，无论 Harshith 如何选择 $3\times 7$ 的矩阵，Aryan 总能找到一个 $2\times 2$ 的所有元素相等的子矩阵。$(3,7)$ 也是所有可能二元组中字典序最小的。

由 ChatGPT 4.1 翻译