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: 2016-08-27 10:30:03

@Blue.Mary; Problem Statement has been updated. Thanks for pointing out :)

[Rampage] Blue.Mary: 2016-08-27 03:42:38

What's the range of N & M? Can N and/or M equal zero?

Last edit: 2016-08-27 03:43:18

Added by:BISHAL GAUTAM
Date:2016-08-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU