牛牛进入了方格世界,方格世界由
个方格构成的高为
宽为
的矩形,牛牛所在的方格为
,而方格世界的出口在
。在方格世界中,牛牛只能向上走或者向左或向右走,而且牛牛走过的方格不能再次进入。牛牛想知道他有多少种走出方格世界的路径,答案可能很大请对
取模。
第一行为一个,表示有
组数据。
接下来有行,每行有两个数字
和
。
输出为行,每行一个数字表示答案。
2 2 2 3 3
2 9
//注意快速幂里a=a*a%mod #include<bits/stdc++.h> using namespace std; typedef long long ll; #define mod 1000000007 //非递归快速幂 ll qpow(ll a, ll n){ ll ans = 1; while(n){ if(n&1) //如果n的当前末位为1 ans =(ans%mod)*(a%mod)%mod; //ans乘上当前的a a=a*a%mod; //a自乘 n >>= 1; //n往右移一位 } return (ans+mod)%mod; } int main(){ ll t; ll n,m; scanf("%lld",&t); while(t--){ scanf("%lld%lld",&n,&m); printf("%lld\n",qpow(m,n-1)); } return 0; }