前言

模板型的题目，需要记录下来。

题目描述

Invoker

On of Vance’s favourite hero is Invoker, Kael. As many people knows Kael can control the elements and combine them to invoke a powerful skill. Vance like Kael very much so he changes the map to make Kael more powerful.
In his new map, Kael can control n kind of elements and he can put m elements equal-spacedly on a magic ring and combine them to invoke a new skill. But if a arrangement can change into another by rotate the magic ring or reverse the ring along the axis, they will invoke the same skill. Now give you n and m how many different skill can Kael invoke? As the number maybe too large, just output the answer mod 1000000007.

Input
The first line contains a single positive integer T( T <= 500 ), indicates the number of test cases.
For each test case: give you two positive integers n and m. ( 1 <= n, m <= 10000 )
Output
For each test case: output the case number as shown and then output the answer mod 1000000007 in a line. Look sample for more information.
Sample Input
2
3 4
1 2
Sample Output
Case #1: 21
Case #2: 1

题目大意

我BB酱作为一名资深DOTA玩家，Kale这个英雄对我来说一直都是在黑名单榜首，复杂的技能操作令我头秃(就好像acm一样)，这个题的背景就是建立在卡尔搓技能的基础上的，不过呢加入了一个特点——组合没有头尾，也就是说aaab和baaa和abaa和aaba都是一样的，在网上很多教程我觉得写得不错，有一种说法是把它看成一个项链，于是题目变成了这样：

有条n长度的项链，m种不同的颜色，问可以组成多少种不同的项链（翻转与旋转后相同的都算是同一条项链）

解题思路

这道题用到了Polya原理和费马小定理，还有快速幂的知识，对我来说还有些复杂，但是这里还是要把这个题记录一下，因为之前见到过很多这样的题，这次也算是整合一个模板吧。

解题代码

总结

还有很多东西需要学，polya原理需要好好看看，希望能有时间吧。