牛牛管理着一片农场，在这片农场的一侧有着 n 块栅栏排成一排，为了给单调的牧场生活增添一份乐趣，牛牛决定为这 n 块栅栏涂色。 现在，牛牛在牧场中一共找到了 m 种不同颜料，为了不让颜色过于单一，牛牛决定相邻的两块栅栏不能使用同一种颜料。 那么，在满足上述前提下，牛牛最终完成的涂色一共会有多少种方案？ 由于答案可能很大，所以只需要求出对 10 ^ 9+ 7 取模后的结果。
本题为多组测试数据，第一行输入一个正整数 T( 1≤ T≤ 1000) ，代表测试数据组数。 对于每组测试数据，一行输入两个正整数 n, m( 1≤ n, m≤ 1000) ，代表栅栏总数以及颜料数量。
对于每组测试数据，输出一行一个数字表示牛牛的涂色方案。
1 2 2
2
考点：组合数学
数据规模 n ≤ 1e3 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出
推荐方向：组合数学
本题切入点
相邻不能同色：第一块有 m 种选择，其后每一块都有 m−1 种，答案 = m×(m−1)^(n−1) 取模。
用计数原理（加法/乘法原理）与组合数公式统计方案数。
思路框架（组合数学 通法 · 非本题专属）
实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。
复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1
1 / 2 22解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：贝壳找房2023届校招测试类试卷。