GOC11B  Sanvi Hates Palindrome
Sanvi is very busy girl. So you have been given enough time (1000 milliseconds) to help him.
Sanvi has a bag of marbles with different alphabets written on them. And she 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 she puts only N marbles (out of M*N) in N boxes, one by one and upon completion she writes down the letters on the marbles on a paper to form a string. As Sanvi hates palindrome strings (strings which read same from both sides e.g. MADAM), she erases palindrome string from the paper as soon as he finds one.
Now she is wondering how many different strings she might get on her paper if she could try all possible combination of putting the marbles in the boxes. So you have to help her by answering. As there could be many strings so print it modulo 1,000,000,007.
Input
Input starts with an integer TC(<=10), denoting the number of test cases. Each case starts with two non negative integers N(<=100000) and M(<=26) as described above.
Output
For each case, print the case number and total number of strings written on the paper modulo 1000000007.
Example
Input: 2
2 2
2 3 Output: Case 1: 2
Case 2: 6
hide comments
BISHAL GAUTAM:
20160827 10:30:03
@Blue.Mary; Problem Statement has been updated. Thanks for pointing out :) 

[Rampage] Blue.Mary:
20160827 03:42:38
What's the range of N & M? Can N and/or M equal zero? Last edit: 20160827 03:43:18 
Added by:  BISHAL GAUTAM 
Date:  20160826 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 