CRCLE_UI  Colorful Circle (EASY)

I take this problem from my midterm exam today, because for me and some of my friends it's interesting, so I decided to translated this problem into english and upload this problem to SPOJ. See the original problem in indonesian language here.

Given N sectors where 1<N<10^{1000}, from a circle that sown in the picture below:
We will color each sector with K different colors, where 2<K<10^{1000} such that each sector colored with one color and each adjacent sector must have different color. Your task is to count how many ways to color all that sectors.
Input
First line, there is a number T(0<T<1000) denoting number of test cases, then T lines follow.
each line containing two integers: N and K separated by a space.
Output
For each test case, output number of ways to color the circle, since the number can be too large, take modulo 10^{9}+7.
Example
Input: 2
2 3
3 3 Output: 6
6
Explanation:
For the first case, we have two sectors and three colors, here is all possibilities:
For second test case, we have three sector and three colors, here is all possibilities:
Time limit set so that ~128 Bytes of python 3 code can get accepted, also my C top speed program AC in 0.12s
Have fun :)
hide comments
julkas:
20180706 14:25:42
Good problem. 

hanstan:
20170713 08:15:09
Nailed it 0.00s :) 

Itachi_Uchiha:
20150123 05:45:42
Tjandra , some more test cases please


Viplov Jain:
20130701 21:20:37
@Tjandra: please look at my submission,why WA? ,submission id>9578731


Yashpal:
20130605 18:42:04
@Tjandra:if i hav to calculate the no. of ways to color the n sectors with all the k colors or taken some colors at a time.....i.e if k<=n or not.... 

maradona:
20130527 08:55:53
@Tjandra my id is 9353125


abdou_93:
20130406 08:56:32
thanks @Tjandra for Reply ... but still WA .... I think i can not AC this problem now :(


abdou_93:
20130404 11:20:23
please @Tjandra ..can you look at my submission (id>9035872)...


Avinash Thummala:
20130116 10:28:01
@Tjandra If possible please have a look at my submission (id>8509987). Quite new to Python, but used it anyway as I thought that Montgomery reduction would be useful.


YangYue:
20130101 03:21:24
I've also thougth about this problem, so

Added by:  Tjandra Satria Gunawan 
Date:  20121114 
Time limit:  0.170s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Discrete Math II, Midterm exam, question number 4, University of Indonesia, 14 November 2012  Translated by: Tjandra 