SP28180 GOC11B - Mr.BG Hates Palindrome

Mr.BG is very busy person. So you have been given enough time (1000 milliseconds) to help him. Mr. BG has a bag of marbles with different alphabets written on them. And he has become busy on playing with these marbles by putting them in N boxes placed in a row. There are exactly M distinct type of marbles, N of each type. Now he puts only N marbles (out of M\*N) in N boxes, one by one and upon completion he writes down the letters on the marbles on a paper to form a string. As Mr.BG hates palindrome strings (strings which read same from both sides e.g. MADAM), he erases palindrome string from the paper as soon as he finds one. Now he is wondering how many different strings he might get on his paper if he could try all possible combination of putting the marbles in the boxes. So you have to help him by answering. As there could be many strings so print it modulo 1,000,000,007.

Input starts with an integer TC(

For each case, print the case number and total number of strings written on the paper modulo 1000000007.