Yuanyuan Long is a dragon like this picture? 

I don’t know, maybe you can ask him. But I’m sure Yuanyuan Long likes ballons, he has a lot of ballons. One day, he gets $n$ white ballons and $k$ kinds of pigment, and he thought a problem: 

1. Number these ballons $b_1, b_2, … , b_i, …,$  to $b_n$. 

2. link these ballons to a circle in order, and color these ballons. 

3. He need to make sure that any neighbor ballons have different colors. 

He wants to know how many solutions to solve this problem. Can you get the answer to him? The answer maybe very large, get the answer MOD $100,000,007$. 

For Example: with 3 ballons and 3 kinds of pigment

Your answer is $3*2*1 \bmod\ 100000007 = 6$. 

The first line is the cases $T\ (T \leq 100)$.

For next $T$ lines, each line contains $n, k\ (2\leq n \leq 10000,\ 2\leq k \leq100)$.