Zombies zombies everywhere!! 
In a parallel world of zombies, there are N zombies. There are infinite number of unused cars, each of same model only differentiated by the their colors. The cars are of K colors.

A zombie parent can give birth to any number of zombie-children (possibly zero), i.e. each zombie will have its parent except the head zombie which was born in the winters by combination of ice and fire.

Now, zombies are having great difficulties to commute to their offices without cars, so they decided to use the cars available. Every zombie will need only one car. Head zombie called a meeting regarding this, in which he will allow each zombie to select a car for him.

Out of all the cars, the head zombie chose one of cars for him. Now, he called his children to choose the cars for them. After that they called their children and so on till each of the zombie had a car. Head zombie knew that it won't be a good idea to allow children to have cars of same color as that of parent, as they might mistakenly use that. So, he enforced this rule during the selection of cars.

Professor James Moriarty is a criminal mastermind and has trapped Watson again in the zombie world. Sherlock somehow manages to go there and met the head zombie. Head zombie told Sherlock that they will let Watson free if and only if Sherlock manages to tell him the maximum number of ways in which the cars can be selected by N Zombies among all possible hierarchies. A hierarchy represents parent-child relationships among the N zombies. Since the answer may be large, output the answer modulo 109 + 7. Sherlock can not compute big numbers, so he confides you to solve this for him.

-----Input-----
The first line consists of a single integer T, the number of test-cases.

Each test case consists of two space-separated integers N and K, denoting number of zombies and the possible number of colors of the cars respectively.

-----Output-----
For each test-case, output a single line denoting the answer of the problem.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10^9
- 1 ≤ K ≤ 10^9

-----Subtasks-----
Subtask #1 : (10 points)
- 1 ≤ T ≤ 20
- 1 ≤ N, K ≤ 10

Subtask 2 : (20 points) 

- 1 ≤ T ≤ 10
- 1 ≤ N, K ≤ 10000

Subtask 3 : (70 points) 

- 1 ≤ T ≤ 100
- 1 ≤ N, K ≤ 10^9

-----Example-----
Input
2
2 2
3 3
Output:
2
12

-----Explanation
In the first sample test case, there are 2 zombies. Let us name them Z1 and Z2. Let one hierarchy be one in which Z1 is parent of Z2. There are 2 colors, suppose red and blue. If Z1 takes red, then Z2 should take a blue. If Z1 takes blue, then Z2 should take red. 
Note that one other possible hierarchy could be one in which Z2 is a parent of Z1. In that hierarchy also, number of possible ways of assigning cars is 2.
So there maximum number of possible ways is 2.

In the second example, we have 3 Zombies say Z1, Z2, Z3 and cars of 3 colors, suppose red, blue and green.
A hierarchy to maximize the number of possibilities is Z1 is the parent of Z2, Z2 is the parent of Z3.
Zombie Z1 can choose one of red, blue or green cars. Z2 can choose one of the remaining two colors (as its car's color can not be same as its parent car.). Z3 can also choose his car in two colors, (one of them could be color same as Z1, and other being the color which is not same as cars of both Z1 and Z2.). This way, there can be 12 different ways of selecting the cars.

-----
In the first sample test case, there are 2 zombies. Let us name them Z1 and Z2. Let one hierarchy be one in which Z1 is parent of Z2. There are 2 colors, suppose red and blue. If Z1 takes red, then Z2 should take a blue. If Z1 takes blue, then Z2 should take red. 

Note that one other possible hierarchy could be one in which Z2 is a parent of Z1. In that hierarchy also, number of possible ways of assigning cars is 2.

So there maximum number of possible ways is 2.

In the second example, we have 3 Zombies say Z1, Z2, Z3 and cars of 3 colors, suppose red, blue and green.

A hierarchy to maximize the number of possibilities is Z1 is the parent of Z2, Z2 is the parent of Z3.

Zombie Z1 can choose one of red, blue or green cars. Z2 can choose one of the remaining two colors (as its car's color can not be same as its parent car.). Z3 can also choose his car in two colors, (one of them could be color same as Z1, and other being the color which is not same as cars of both Z1 and Z2.). This way, there can be 12 different ways of selecting the cars.

Difficulty: interview

Starter code:

Solutions:
ways=x=0
val=10**9
remi=((10**9)+7)
t=int(input())
for i in range(t):
 n,k=list(map(int,input().split()))
 if t<=100 and n>=1 and k<=val:
  x=(k-1)**(n-1)
  ways=k*x
  ways=ways%remi
  print(ways)
  x=ways=0
 else:
  break

test = int(input())
for i in range (1,test+1):
 a = input().split(" ")
 n = int(a[0])
 k = int(a[1])
 ans = pow(k-1,n-1,1000000007)
 ans = (ans*k)%1000000007
 print(ans)

t = int(input());
for i in range(0 ,t):
 n = input().split(" ");
 n1 = int(n[0])
 k = int(n[1])
 ax = pow(k-1,n1-1,1000000007);
 ax = ((ax%1000000007)*(k%1000000007))%1000000007
 print(ax)

# your code goes here
import sys 
t = eval(input())
for i in range(0,t):
 a,b = list(map(int, sys.stdin.readline().split(' ')))
 if(b==1):
  print(0)
 else: 
  ans=b*((b-1)**(a-1))%1000000007
  print(ans)

# your code goes here
t = eval(input())
for i in range(0,t):
 a,b=list(map(int,input().split()))
 if(b==1):
  print(0)
 else: 
  ans=b*((b-1)**(a-1))
  ans=ans%1000000007
  print(ans)

t = eval(input(""))
 
while(t>0):
 n,k = list(map(int,input().split()))
 
 if(k==1):
  if(n==1):
   ans=k;
   print(ans)
   
 else:
  ans=k;
  n=n-1
  k=k-1
  p=1
  while(n>0):
   p=p*k
   p=p%1000000007
   n=n-1
  
  
  ans=(ans*p)%1000000007
 
  print(ans)
  
  
 t=t-1 

# cook your code here
mod=10**9
mod+=7
t=input()
t=int(t)
while(t>0):
 z=input()
 N,K=z.split(' ')
 N=int(N)
 K=int(K)
 t-=1
 if (N==1):
  print(K)
 elif (K==1):
  print(0)
 elif (K==2):
  print(2)
 else:
  res=pow(K-1,N-1,mod)
  res*=K
  res%=mod
  print(res)

# Recursive power function that evaluates in O(log n)
def power(x, y):
 if y == 0:
  return 1
 else:
  temp_val = power(x, y // 2)
  if y % 2 == 0:
   return( (temp_val * temp_val) % 1000000007 )
  else:
   return( (temp_val * temp_val * x) % 1000000007 )

def __starting_point():
 # Read number of cases
 T = int(input())
 # Run a loop for all test cases
 for i in range(T):
  # Read values
  N, K = list(map(int, input().split()))

  val = K * power(K - 1, N - 1)
  print(val % 1000000007)

__starting_point()

# Recursive power function that evaluates in O(log n)
def power(x, y):
 if y == 0:
  return 1
 else:
  temp_val = power(x, y // 2)
  if y % 2 == 0:
   return( (temp_val * temp_val) % 1000000007 )
  else:
   return( (temp_val * temp_val * x) % 1000000007 )

def __starting_point():
 # Read number of cases
 T = int(input())
 # Run a loop for all test cases
 for i in range(T):
  # Read values
  N, K = list(map(int, input().split()))

  val = K * power(K - 1, N - 1)
  print(val % 1000000007)

__starting_point()

from math import pow
t=input()
t=int(t)
while t>0:
 n,k=input().split()
 n=int(n)
 k=int(k)
 p=pow(k-1,n-1)
 tot=(k*p)%(pow(10,9)+7)
 print(int(tot))
 t=t-1

from math import pow
t=input()
t=int(t)
while t>0:
 n,k=input().split()
 n=int(n)
 k=int(k)
 p=pow(k-1,n-1)
 tot=(k*p)%(pow(10,9)+7)
 print(int(tot))
 t=t-1

def __starting_point():
 # Read number of cases
 T = int(input())
 # Run a loop for all test cases
 for i in range(T):
  # Read values
  N, K = list(map(int, input().split()))

  val = K * pow(K - 1, N - 1)
  print(val % 1000000007)

__starting_point()

t = eval(input())

for _ in range(t):
 n, k = list(map(int, input().split()))
 ans = k*((k-1)**(n-1))
 print(ans%1000000007)

import math
MOD=1000000007
def fast_exp(base,exp):
 res=1;
 while(exp>0):
  if(exp%2==1):
   res=(res*base)%MOD
  base=(base*base)%MOD
  exp/=2;
 return res
 
for t in range(int(input())):
 
 pro=1
 a,b=list(map(int,input().split()))
 #for i in xrange(a):
 pro*=b
  
 pro*=fast_exp((b-1),(a-1))
 
 print(pro%MOD) 


mod = 1000000007
for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 x = (k%mod) * pow(k-1,n-1, mod)
 print(x%mod)

import math

for t in range(int(input())):
 mod=1000000007
 pro=1
 a,b=list(map(int,input().split()))
 for i in range(a):
  if(i==0):
   pro*=b
  else:
   pro*=((b-1))
   if(pro>mod):
    pro%=mod
 print(pro%mod) 


t=int(input())
def haha(x,y,p):
 ans = 1 
 x = x % p 
 while (y > 0):           
  if (y % 2!=0):
   ans = (ans*x) % p; 
  y = y/2;
  x = (x**2) % p;      
 return ans
while t>0:
 t-=1
 n,k=list(map(int,input().split()))
 m=1000000007
 print(((k%m)*(haha(k-1,n-1,m))%m)%m)

import sys
t=int(eval(input("")))
while t:
 m,n=list(map(int,sys.stdin.readline().split()))
 prod=n
 prod*=pow((n-1),(m-1),1000000007)
 print(prod%1000000007)
 t-=1


M=1000000007
def expmod_iter(a,b,c):
 x = 1
 while(b>0):
  if(b&1==1): x = (x*a)%c
  a=(a*a)%c
  b >>= 1
 return x%c

t=eval(input())
while t>0:
 t-=1
 n,k=list(map(int,input().split()))
 if n>=2 and k<=1:
  print(0)
 else:
  print((k*expmod_iter(k-1,n-1,M))%M)

import sys
t=int(eval(input("")))
while t:
 m,n=list(map(int,sys.stdin.readline().split()))
 prod=n
 prod*=(n-1)**(m-1)
 print(prod%1000000007)
 t-=1


import sys
t=int(eval(input("")))
while t:
 m,n=list(map(int,sys.stdin.readline().split()))
 prod=n
 for i in range(m-1):
  prod*=n-1
 print(prod%1000000007)
 t-=1