Counting Necklaces
Count the distinct necklaces of N beads using up to K colours, where rotations are considered identical, modulo 109+7.
Input: one line with two integers N and K.
Output: the necklace count mod 109+7.
Constraints:
- 1 ≤ N ≤ 109
- 1 ≤ K ≤ 109
Sample Tests
Input 1
3 2
Output 1
4
Input 2
1 5
Output 2
5
Discussion (opens after you solve — no spoilers before)
No comments yet.