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, separated 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.


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

hide comments
2024-08-02 17:46:39
@tjandra
Hello there
Can you explain the optimal solution for me?
2013-07-19 03:00:37 darryl
The time limit is not strict. Just need some observation to clear it.
2012-12-13 08:22:47 (Tjandra Satria Gunawan)(曾毅昆)
@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
2012-12-12 08:00:08 YangYue
nice problem
but the time limit is so strict
I AC it by onstant optimization

Last edit: 2012-12-12 11:36:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.