最近古yu迷上了《恋与制作人》，天天嚷嚷着白起我老公(死gay死gay的),白起又向古yu提出了一个问题：
给你n种卡牌（数量无限）,将其摆成长度为m的圆环的方案数。
(如果这个环可以通过若干次旋转或者反方向读(（abc）(cba)是一样的),则认为他们是一样的)
这时古yu一脸茫然，大哭特苦不能守护白起了。古yu希望你能帮助他解决这个问题去守护白起。
输入描述:
第一行一个t(0<t<=500)
接下来t行，每行俩个正整数n,m(1<=n,m<=10000)
输出描述:
一个答案加换行(答案可能很大，所以取模1000000007)
示例1
说明
对于第一个样例有21种不同的方法
/ aaaa / aaab / aaac / aabb / aabc / aacc / abab /
/ abac / abbb / abbc / abcb / abcc / acac / acbc /
/ accc / bbbb / bbbc / bbcc / bcbc / bccc / cccc