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 n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma celor n numere citite.

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$.