A Boring Question
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 865 Accepted Submission(s): 534
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)
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
1 2
2 3
Sample Output
3
13
13
Author
UESTC
Source
Recommend
wange2014
题解：
找规律...
f(0,2)=1; f(1,2)=3; f(2,2)=7; f(3,2)=15
f(0,3)=1; f(1,3)=4; f(2,3)=13;
f(0,4)=1; f(1,4)=5; f(2,4)=21;
f(0,5)=1; f(1,5)=6; f(2,5)=31;
f(n,m)=f(n-1,m)*m+1
所以 f(n,m)=(m^(n+1)-1)/(m-1)
//#include <iostream>
#include<bits/stdc++.h> using namespace std; const long long mod=;
long long ans,n,m;
int T;
long long poww(long long a,long long b)
{
long long ans=;
while(b)
{
if (b%==) ans=(ans*a)%mod;
a=(a*a)%mod;
b/=;
}
return ans;
} int main()
{
scanf("%d",&T);
for(;T>;T--)
{
scanf("%lld%lld",&n,&m);
long long ans=poww(m,n+);
ans=(ans+mod-)%mod;
ans=(ans*poww(m-,mod-))%mod;
printf("%lld\n",ans);
}
return ;
}