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.
hide comments
yazan_kh44:
2024-08-02 17:46:39
@tjandra
|
|
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
|
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 |