## PSTR - Number of Prime Strings

no tags

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:12 3Output:6ExplanationThe 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: 2013-07-19 03:00:37 The time limit is not strict. Just need some observation to clear it. (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-12-13 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: 2012-12-13 09:18:07 YangYue: 2012-12-12 08:00:08 nice problem but the time limit is so strict I AC it by onstant optimization Last edit: 2012-12-12 11:36:49

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