Cerința

Astăzi în clasa 0 profesoara a numit Q copii și le-a dat 3 numere, a, b și c, copiii trebuiau să spună care este rezultatul calculului \({a}^{{C}_{b}^{c}}\), adică \({a}^{ \frac{b! }{{c! *(b-c)! }}}\), modulo \(10^9+7\). Copiii nu au știut să răspundă la întrebări așa că voi trebuie acuma să le spuneți rezultatul.

Date de intrare

Programul citește de la tastatură numărul Q, iar apoi Q triplete a b c, cu semnificația din enunț.

Date de ieșire

Programul va afișa Q numere, fiecare pe o linie, reprezentând răspunsul pentru tripleta corspunzătoare.

Restricții și precizări

• 1 ≤ Q ≤ 10.
• 1 ≤ a,b,c ≤ 1.000.000.
• c ≤ b.

Exemplu:

Intrare

3
1 5 5
2 10 2
3 9 4

Ieșire

1
371842544
665507626

Explicație

Pentru primul exemplu: \({C}_{5}^{5} = 1\), \(1^1 = 1\).