A Boring Question
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 487 Accepted Submission(s):
271
Problem Description
There are an equation.
∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007=?
We define that (kj+1kj)=kj+1!kj!(kj+1−kj)! . And (kj+1kj)=0 while kj+1<kj .
You have to get the answer for each n and m that given to you.
For example,if n=1 ,m=3 ,
When k1=0,k2=0,k3=0,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=0,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=0,k2=0,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=1,k2=0,k3=1,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=1,(k2k1)(k3k2)=1 .
So the answer is 4.
∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007=?
We define that (kj+1kj)=kj+1!kj!(kj+1−kj)! . And (kj+1kj)=0 while kj+1<kj .
You have to get the answer for each n and m that given to you.
For example,if n=1 ,m=3 ,
When k1=0,k2=0,k3=0,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=0,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=0,k2=0,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=1,k2=0,k3=1,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=1,(k2k1)(k3k2)=1 .
So the answer is 4.
Input
The first line of the input contains the only integer
T ,(1≤T≤10000)
Then T lines follow,the i-th line contains two integers n ,m ,(0≤n≤109,2≤m≤109)
T ,(1≤T≤10000)
Then T lines follow,the i-th line contains two integers n ,m ,(0≤n≤109,2≤m≤109)
Output
For each n and m ,output the answer in a single line.
Sample Input
2
1 2
2 3
Sample Output
3
13
Author
UESTC
题意：根据题目中规定的结算方式，给定n,m的值，求结果。
打表找规律，比赛的时候找到了还是没写出来。。因为有除法还有取模，所以要用到逆元，第一次使用逆元，找了一个模板。
附上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long
#define mod 1000000007
using namespace std; ll mat(ll a,ll b)///a^b，结果对mod取膜，b的值很大的时候
{
ll c=;
if(b==) return a%mod; ///当b为1时，只剩下最后一个a
else if(b&) ///b为奇数
return mat(a,b-)*a%mod; ///把单独的a拿出来
else ///b为偶数
return mat(a*a%mod,b/)%mod; ///直接相乘，系数除以2
} ll extend_gcd(ll a,ll b,ll &x,ll &y)
{
if(a==&&b==) return -;//无最大公约数
if(b==){x=;y=;return a;}
ll d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
ll mod_reverse(ll a,ll n)
{
ll x,y;
ll d=extend_gcd(a,n,x,y);
if(d==) return (x%n+n)%n;
else return -;
} ll c(ll n,ll m)
{
ll i,j,t1,t2,ans;
t1=((mat(m,n+)-)%mod+mod)%mod;
t2=(m-)%mod;
return t1*mod_reverse(t2,mod)%mod;
} int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ll ans=c(n,m);
printf("%I64d\n",ans);
}
return ;
}