宇宙大帝 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
对于 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。