最近古yu迷上了《恋与制作人》，天天嚷嚷着白起我老公(死gay死gay的),白起又向古yu提出了一个问题： 给你n种卡牌（数量无限）,将其摆成长度为m的圆环的方案数。 (如果这个环可以通过若干次旋转或者反方向读(（abc）(cba)是一样的),则认为他们是一样的) 这时古yu一脸茫然，大哭特苦不能守护白起了。古yu希望你能帮助他解决这个问题去守护白起。

输入描述:

第一行一个t(0接下来t行，每行俩个正整数n,m(1=n,m=10000)

输出描述:

一个答案加换行(答案可能很大，所以取模1000000007)