3699: 旋律的总数(第六轮01)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
牛牛最近在思考，音乐的主旋律似乎数目是有限的。
真正的音乐旋律比较复杂，为了简化问题，牛牛把旋律简化成一个长度为n的时 间相关的序列 a1 ~ an 。
序列可以填入的数字为1 ~ m 。
但是对于转调前后的旋律应当被认为是一致的，换言之，如果序列 ∃k, ∀i, ai ≡ bi + k(modm)
则视为a 序列和b序列是相同的。
牛牛想知道对于给定的n 和m，有多少种这样的旋律，也就是有多少个各不相同 的序列a 。
答案对109 + 7取模。
输入
第一行输入一个整数T表示数据组数。
随后T行，每行输入两个整数n, m，用一个空格隔开，表示序列长度和序列范围。
输出
输出T行，每行输出一个整数ans ，表示对应的答案 。
样例输入 复制
2
1 12
3 2样例输出 复制
1
4提示
【样例 1 输入】
2
1 12
3 2
【样例 1 输出】
1
4
【样例 1 说明】
样例 1 只有一种情况， (1)。
样例 2 只有(1,1,1),(1,1,2),(1,2,1),(1,2,2)， 4 种情况。
【样例 2 输入】
1
1474 12
【样例 2 输出】
908395824
【样例 2 说明】
该样例作为大样例。
对于 20%的数据有n, m ≤ 3
对于 40%的数据有n, m ≤ 6
对于 70%的数据有n ≤ 10^6, m ≤ 12
对于 100%的数据有T ≤ 10,1 ≤ n ≤ 10^9, 1 ≤ m ≤ 10^6 。