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 letters 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 she 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