Description

七夕就要到了，大师兄要送给他的女朋友一条项链。
他买回了一条有\(n\)个插槽的项链胚子，决定自己往上镶嵌钻石，钻石一共有\(m\)种不同的颜色。
如果两条项链可以通过旋转而重合，即能在两条项链上各选定一个起点，使得对于所有的自然数\(i\)，两个项链从各自起点开始逆时针第\(i\)个位置的钻石颜色都相同，那么这两条项链就被视为相同。
这时，大师兄醒了，才意识到他并没有什么女朋友。
于是他关心起了一个非常无聊的问题：一共有多少本质不同的项链？
请注意，你不能翻转项链，只能在同一个平面内旋转项链。

Format

Input

每个测试点包含至多\(1000\)组数据，请处理至文件结束。
每组数据包含一行两个空格隔开的整数\(n,m(1<=n,m<=10^9)\)。

Output

按照输入顺序，对于每组数据，输出一行一个整数，表示对应的答案除以\(10^9+7\)所得余数。

Sample 1

Input

4 3
6324 6324

Output

24
231909625

Limitation

1s, 1GB for each test case.

Source

Vijos Original