PSTR  Number of Prime Strings
A string is called a "prime string" if it can't be written as concatenation of more than one same strings. For example, the following strings are not prime strings: AAA, ABABAB, CFGFGCFGFG, while CFGFGC, ABABA are prime strings.
Calculate the number of prime string of length N (1<=N<=1000000), and only contains first K (1<=K<=26) letters from English alphabet. Note that some of these K letters need not appear in that string.
Input
Multiple test cases. The number of them (about 10000) is given in the very first line.
Each test case contains one line with two integers  K and N, seperated by a single space.
Output
For each test case, output the required number modulo 1000000007 in a single line.
Example
Input:
1
2 3
Output:
6
Explanation
The prime strings of length 3 which only contain character 'A' and 'B' are: AAB,ABA,ABB,BAA,BAB,BBA.
Constraints
1 <= N <= 1000000 1 <= K <= 26
Total number of test cases is around 10000.
hide comments
darryl:
20130719 03:00:37
The time limit is not strict. Just need some observation to clear it. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121213 08:22:47
@YangYue: I'm sorry, but I think time limit is not too strict, this problem can be solved under 0.1s without any large precomputation... time limit is about 11 times slower than optimal solution... Last edit: 20121213 09:18:07 

YangYue:
20121212 08:00:08
nice problem

Added by:  Kunal Jain 
Date:  20110207 
Time limit:  0.133s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  CodeCraft 11 