Supărat că fata de care-i plăcea l-a respins, Bogdan și-a făcut bagajele și a pornit într-o excursie de-a lungul întregii lumi. Acesta a vizitat mai toate continentele, însă acum este blocat în Africa din cauza faptului că Bogdan, băiat mai neastâmpărat din fire, s-a apucat să se bată cu țânțarii Mosquito.Bineînțeles că a fost înțepat și că acum trebuie să caute antidot pentru venin, altfel Bogdan se va transforma și el în Mosquito. Acesta s-a dus să-i ceară ajutorul lui Aashiq, care îi spune următoarele: “Te voi vindeca de înțepături dacă reușești să duci la bun sfârșit sarcina pe care ți-o dau.”, însă Bogdan nu prea se pricepe la sarcini complicate, așa că vă roagă să rezolvați voi cerința în locul lui.

Cerința

Dându-se trei numere naturale, a, n, k, trebuie să aflați valoarea următoarei expresii: ak•ak+2k•...•ak+2k+...+nk. Antidotul pentru înțepăturile de Mosquito necesită foarte multă muncă, motiv pentru care vor trebui îndeplinite t teste.

Date de intrare

Fișierul de intrare mosquito.in conține pe prima linie numărul t, reprezentând numărul de teste.Pe următoarele t linii se vor afla câte trei numere a, n, k, separate prin spații, reprezentând valorile pentru expresia cu numărul t. Fiind un număr foarte mare, rezultatul se va tipări modulo 1000000007.

Date de ieșire

Fișierul de ieșire mosquito.out va conține pe linia t răspunsul pentru testul nu numărul de ordine t.

Restricții și precizări

• 1 ≤ t ≤ 5
• 1 ≤ a, n, k, ≤ 109
• Se garantează faptul că niciuna dintre puterile lui a nu va depăși 1018

Exemplul 1:

mosquito.in

1
2 3 1

mosquito.out

1024

Exemplul 2:

mosquito.in

1
3 4 1

mosquito.out

486784380