Ариан и Харшит играют в игру. У них есть три числа. $$$a$$$, $$$b$$$ и $$$k$$$. Затем Ариан даёт Харшиту два целых числа $$$n$$$ и $$$m$$$. После этого Харшит даёт Ариану матрицу $$$X$$$ из $$$n$$$ строк и $$$m$$$ столбцов, причём каждый элемент $$$X$$$ находится в диапазоне от $$$1$$$ до $$$k$$$ (включительно). Ариан выигрывает, если он может найти подматрицу$$$^{\text{∗}}$$$ $$$Y$$$ матрицы $$$X$$$ из $$$a$$$ строк и $$$b$$$ столбцов такую, что все элементы $$$Y$$$ равны между собой.
Например, если $$$a=2, b=2, k=6, n=3$$$ и $$$m=3$$$, и Харшит даёт Ариану следующую матрицу, то Ариан выигрывает, так как в ней есть подматрица размера $$$2\times 2$$$, все элементы которой равны $$$1$$$, как показано ниже.
Пример матрицы, для которой Ариан выигрывает Ариан даёт вам значения $$$a$$$, $$$b$$$ и $$$k$$$. Он просит вас найти лексикографически минимальную пару $$$(n,m)$$$, которую он должен дать Харшиту, чтобы Ариан всегда выигрывал. Помогите Ариану выиграть игру. Считайте, что Харшит играет оптимально. Значения $$$n$$$ и $$$m$$$ могут быть большими, поэтому выводите их по модулю $$$10^9+7$$$. Пара $$$(n_1, m_1)$$$ лексикографически меньше пары $$$(n_2, m_2)$$$, если либо $$$n_1 \lt n_2$$$, либо $$$n_1=n_2$$$ и $$$m_1 \lt 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)$$$ — лексикографически минимальная пара среди всех возможных.
Во втором наборе входных данных можно убедиться, что какую бы матрицу $$$3\times 7$$$ Харшит ни дал Ариану, Ариан всегда сможет найти подматрицу $$$2\times 2$$$ с одинаковыми элементами. Также, $$$(3,7)$$$ — лексикографически минимальная пара среди всех вариантов, при которых Ариан выигрывает.
