Chosen by god
Everyone knows there is a computer game names "hearth stone", recently xzz likes this game very much. If you want to win, you need both capacity and good luck.
There is a spell card names "Arcane Missiles", which can deal 3 damages randomly split among all enemies.
xzz have a "Arcane Missiles Plus" can deal n damage randomly split among all enemies. The enemy battle field have only two characters: the enemy hero and enemy minion.
Now we assume the enemy hero have infinite health, the enemy minion has m health.
xzz wants to know the probability of the "Arcane Missiles Plus" to kill the enemy minion (the minion has not more than 0 health after "Arcane Missiles Plus"), can you help him?
Input
The first line of the input contains an integer T, the number of test cases. T test cases follow. (1 ≤ T ≤ 100000)
Each test case consists of a single line containing two integer n and m. (0 ≤ m ≤ n ≤ 1000)
Output
For each test case, because the probability can be written as x / y, please output x * y^-1 mod 1000000007. .(y * y^-1 ≡ 1 mod 10^9 + 7)
Sample Input
2
3 3
2 1Sample Output
125000001
750000006题意：
给出T组n和m n代表你有n发子弹 敌人有两个 一个血量无穷大 一个为m 每次击中敌人都会掉1滴血 问把血量为m的敌人打死的几率有多大 每次开枪随机打中其中一个敌人
思路：
概率问题 先找所有情况 2^n 击中的概率 c(n,m)+c(n,m+1)+……+c（n,n）
所以p=c(n,m)+c(n,m+1)+……+c（n,n)/2^n
看到组合数求和就有点怕了 想到了组合数打表 之前只是听到过
杨辉三角打表组合数、组合数求和：
AC代码：
下面代码里面也用到了取余的公式 特别是减法 WA了好多次：https://mp.csdn.net/postedit/89529166
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
using namespace std;
typedef long long LL;
const int MAX=1e6;
const LL mod=1e9+7;
const LL INF=0x3f3f3f3f;
LL qpow(LL m,LL q)
{
LL ans=1;
while(q){
if(q%2){
ans=ans*m%mod;
}
m=m*m%mod;
q/=2;
}
return ans%mod;
}
LL getinv(LL x,LL y)
{
LL ans=qpow(x,y-2)%mod;
return ans;
}
LL c[1005][1005],sum[1005][1005];
void getc()
{
c[0][0]=1,sum[0][0]=1;
for(int i=1;i<=1001;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i){
c[i][j]=1;
}
else{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
if(j==0){
sum[i][j]=1;
}
else{
sum[i][j]=(sum[i][j-1]+c[i][j])%mod;
}
}
}
}
int main()
{
getc();
LL T,n,m;
cin>>T;
while(T--){
LL num=0,sum1=0;
cin>>n>>m;
num=(sum[n][n]-sum[n][m-1]+mod)%mod;
sum1=getinv(qpow(2,n),mod);
sum1=(sum1*num)%mod;
cout<<sum1<<"\n";
}
return 0;
}