3133

3133. 串珠子

题目

给定 $M$ 种不同颜色的珠子，每种颜色的珠子的个数都足够多。

现在要从中挑选 $N$ 个珠子，串成一个环形手链。

请问一共可以制作出多少种不同的手链。

注意，如果两个手链经旋转或翻转后能够完全重合在一起，对应位置的珠子颜色完全相同，则视为同一种手链。

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 $M,N$。

最后一行包含 0 0 表示输入结束。

输出格式

每组数据输出一个占一行的整数表示结果。

数据范围

$N,M > 0$,

$N \times M \le 32$

输入样例：

1 1
2 1
2 2
5 1
2 5
2 6
6 2
0 0

输出样例：

1
2
3
5
8
13
21

样例解释

当 $M=2,N=5$ 时，一共可以制作出 $8$ 种不同的手链，如下图。

题解