小辣在玩奇怪的的小游戏。

在之前的关卡中，主角收集到了很多的金币，这一关的任务是击败$BOSS$。

在前面的游戏中，主角收集了$m$种技能，在攻击$BOSS$的时候，主角有$n$次选择技能的机会，在每次选择技能时，主角会从他已经收集的技能中等概率随机选择一个加入技能使用序列中，每种技能可以被多次加入使用序列。

在技能选择完成后，主角获得了一个长度为$n$的技能使用序列，此时，主角会将$n$个技能全部施放，随后会对于每种技能进行伤害的结算，对于第$i$个技能，如果该技能被施放了$x$次，将会对$BOSS$造成x²点伤害(如果一个技能从未被施放，那么将不会对$BOSS$造成伤害)。

小辣现在想知道对于所有可能的技能选择结果，他可以期望对$BOSS$造成多少点伤害，请输出答案对10⁹+7取模的结果。

第一行输入一个正整数$1\le T\le 10$,表示数据组数。

对于每组数据：

输入一行两个正整数n m (1≤n≤10⁵,1≤m≤10⁷),代表技能序列的长度和技能的种类数。