Masala #1177

Xotira 16 MB Vaqt 1000 ms
14

FEKUB - Faktoriallik EKUB

Sizga n, a, b sonlari berilgan. n sonining a factorial darajasi va n sonining b factorial darajasining Eng katta umumiy bo'luvchisini toping. Aniqroq qilib aytadigan bo'lsak quyidagini toping.

                                     EKUB(\(n^{a!}\),\(n^{b!}\)

Agar yechim juda ham katta bo'lib ketadigan bo'lsa, yechimning 1000000007 ga qoldig'ini chop eting.


Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T ( 1 ≤ T ≤ \(10^5\)) - testcaselar soni
Har bir T uchun yagona qatorda a, b, n ( 1 ≤ a, b, n ≤ \(10^5\))


Chiquvchi ma'lumotlar:

Har bir T uchun yagona qatorda yechimni chop eting.


Misollar
# input.txt output.txt
1
4
3 1 2
3 3 1
2 5 1
3 4 5
2
1
1
15625