题目描述

宇宙大帝 Luke 拥有一颗璀璨的星球，名为 Lu3KO5（鲁星），这颗星球上存在着一块古老的圆形祭坛。祭坛由 $n$ 个扇形石板组成，每一块石板都有细微的不同。为了能够让祭坛展现出其神秘的力量，Luke 需要用 $m$ 种不同颜色的神秘能量将这些石板染色（每一块石板都必须染色）。

然而，为了保持祭坛的神圣与美观，Luke 要求相邻的两块扇形石板不能染成同一种颜色的能量。现在，Luke 想知道共有多少种不同的染色方案能够满足这个要求（只要有一个位置的石板颜色不同就算不同的染法）。

作为宇宙大帝，Luke 一眼就能看出答案，但他认为这对他来说太过简单，于是将问题交给了聪明的你。你能帮助他计算出所有可能的染色方案吗？

输入格式

输入第一行为一个正整数 $T$，表示 $T$ 组数据。

接下来 $T$ 行每行两个正整数 $n$ 和 $m$。

输出格式

对于每一组数据输出一个整数，表示染色方案数量模 $1000000007$ 后的结果。

样例输入 #1

7
1 1 
3 5 
5 5 
4 4 
1 2
100000 20
1000000000 50

样例输出 #1

1 
60 
1020 
84 
2
904841590
672511614

数据范围

对于 $20\%$ 的数据，$1 \le T \le 5，1 \le n \le m \le 5$。

对于 $50\%$ 的数据，$1 \le T \le 5，1 \le n \le 10^6$。

对于 $100\%$ 的数据 $1 \le T \le 10^5，1 \le n \le 10^9，1 \le m \le 50$。