4376: C. 鲁的石板 (stone.c/cpp/pas)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
### 题目背景
宇宙大帝 Luke 拥有一颗璀璨的星球，名为 Lu3KO5（鲁星），这颗星球上存在着一块古老的圆形祭坛。祭坛由 $n$ 个扇形石板组成，每一块石板都有细微的不同。为了能够让祭坛展现出其神秘的力量，Luke 需要用 $m$ 种不同颜色的神秘能量将这些石板染色（每一块石板都必须染色）。
然而，为了保持祭坛的神圣与美观，Luke 要求相邻的两块扇形石板不能染成同一种颜色的能量。现在，Luke 想知道共有多少种不同的染色方案能够满足这个要求（只要有一个位置的石板颜色不同就算不同的染法）。
作为宇宙大帝，Luke 一眼就能看出答案，但他认为这对他来说太过简单，于是将问题交给了聪明的你。你能帮助他计算出所有可能的染色方案吗？
输入
### 输入格式
输入第一行为一个正整数 $T$，表示 $T$ 组数据。
接下来 $T$ 行每行两个正整数 $n$ 和 $m$。
输出
### 输出格式
对于每一组数据输出一个整数，表示染色方案数量模 $1000000007$ 后的结果。
样例输入 复制
7
1 1
3 5
5 5
4 4
1 2
100000 20
1000000000 50样例输出 复制
1
60
1020
84
2
904841590
672511614提示
### Examples
#### 【样例 1 输入】
```input
7
1 1
3 5
5 5
4 4
1 2
100000 20
1000000000 50
```
#### 【样例 1 输出】
```output
1
60
1020
84
2
904841590
672511614
```
### Notes
对于 $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$。