Aryan 和 Harshith 玩游戏。它们都以三个整数 $$$a$$$、$$$b$$$ 和 $$$k$$$ 开头。然后 Aryan 给 Harshith 两个整数 $$$n$$$ 和 $$$m$$$。然后,Harshith 给 Aryan 一个矩阵 $$$X$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,使得 $$$X$$$ 的每个元素都在 $$$1$$$ 和 $$$k$$$(包含)之间。之后,如果 Aryan 能找到 $$$X$$$ 的子矩阵 $$$^{\text{∗}}$$$ $$$Y$$$ 且具有 $$$a$$$ 行和 $$$b$$$ 列,使得 $$$Y$$$ 的所有元素都相等,则他获胜。
例如,当 $$$a=2、b=2、k=6、n=3$$$ 和 $$$m=3$$$ 时,如果 Harshith 向 Aryan 提供下面的矩阵,则 Aryan 获胜,因为它的子矩阵大小为 $$$2\times 2$$$,所有元素都等于 $$$1$$$,如下所示。
Aryan 获胜的矩阵示例 Aryan 为您提供 $$$a$$$、$$$b$$$ 和 $$$k$$$ 的值。他要求你找到按字典顺序排列的最小元组 $$$(n,m)$$$,他应该将其交给 Harshith,以便 Aryan 始终获胜。帮助雅利安赢得比赛。假设 Harshith 发挥最佳。 $$$n$$$ 和 $$$m$$$ 的值可能很大,因此输出它们对 $$$10^9+7$$$ 取模。如果 $$$n_1 \lt n_2$$$ 或 $$$n_1=n_2$$$ 且 $$$m_1 \lt m_2$$$,则元组 $$$(n_1, m_1)$$$ 按字典顺序小于 $$$(n_2, m_2)$$$。
$$$^{\text{*}}$$$矩阵的子矩阵是通过从原始矩阵中删除一些行和/或列来获得的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 取模。
示例
输入复制
31 1 52 2 290000 80000 70000
输出复制
1 1 3 7 299929959 603196135
注意
对于第一个测试用例,每个 $$$n\times m$$$ 矩阵包含一个 $$$1\times 1$$$ 子矩阵,且所有元素都相等。 $$$(1,1)$$$ 是所有元组中按字典顺序排列的最小元组。
对于第二个测试用例,可以验证无论 Harshith 给 Aryan 提供 $$$3\times 7$$$ 矩阵,Aryan 总是可以通过找到所有元素相等的 $$$2\times 2$$$ 子矩阵来获胜。 $$$(3,7)$$$ 也是所有可能元组中按字典顺序排列的最小元组,Aryan 总是获胜。