分析：
種種神奇的原因（TYP對TLY無腦崇拜，TLY證了一個結論，TYP就說TLY把這題秒了），導緻我以為是結論題，猜了半天。。。F***
其實是一道有點坑的組合計數。
首先，要明确題意：這題問的是在已确定輸赢次數條件下機率，換句話說，每種局面發生的機率相同，且和為1。題目中給出的p是沒用的。
要輸出一個分數，分母很好求，就是一個組合數 C ( n + m , n ) C(n+m,n) C(n+m,n)
分子如果O(N)也很好算：
枚舉最終得分k，可以算出答案為k的方案數：
K确定後，就能知道0分狀态下輸掉的次數。受到NOI2018D1T2冒泡排序的啟發，我們可以用一條在網格上的路徑來表示一種局面。
（上圖是k=n-m時的某種方案，此時不存在0分時失敗的情況）
每往上走一步，就代表勝利一次，往下走一步就代表失敗一次。
為了保證合法性，不能碰到y=-1這條線。而碰到這條線的方案數為C(n+m,n+1)（可以将第一次與x軸接觸的地方，将前半部分上下翻轉，起點就一定會變為點(0,-1)，相當于從(0,-1)到達(n+m,n-m)的路徑數）
此時的方案數為碰到y=0的方案數-碰到y=-1的方案數=C(n+m,n)-C(n+m,n+1)
這是k=n-m+1時的某種方案，此時有且僅有一次在0分時失敗的情況，此時分數不降，友善起見，我們可以先把這一分先加上，使得圖像保持隻向上/向下。
這時，為了保證方案的合法性（即存在“0分時失敗”的情況），我們要求其必然至少一次碰到y=0這條線，那麼此時的方案數應該為：碰到y=0的方案數-碰到y=-1的方案數=C(n+m,n+1)-C(n+m,n+2)
……
是以，就可以得到最終的答案：
∑ k = n − m k ≤ n k ∗ ( C ( n + m , k + m ) − C ( n + m , k + m + 1 ) ) \sum_{k=n-m}^{k\leq n}k*(C(n+m,k+m)-C(n+m,k+m+1)) k=n−m∑k≤nk∗(C(n+m,k+m)−C(n+m,k+m+1))
這是對于 n ≥ m n\geq m n≥m的情況，而對于 n < m n<m n<m的情況，則并沒有太大差別（其實是完全一樣的，隻不過還要限制最終得分非負）
這就是 O ( N T ) O(NT) O(NT)算法了。（為什麼這就值30分？？？）
最後就比較套路了：
這個式子可以通過拆開括号：
( n − m ) C ( n + m , n ) − ( n − m ) C ( n + m , n + 1 ) (n-m)C(n+m,n)-(n-m)C(n+m,n+1) (n−m)C(n+m,n)−(n−m)C(n+m,n+1)
+ ( n − m + 1 ) C ( n + m , n + 1 ) − ( n − m + 1 ) C ( n + m , n + 2 ) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +(n-m+1)C(n+m,n+1)-(n-m+1)C(n+m,n+2) +(n−m+1)C(n+m,n+1)−(n−m+1)C(n+m,n+2)
+ … … +…… +……
領位相減： ( n − m ) C ( n + m , n ) + C ( n + m , n + 1 ) + C ( n + m , n + 2 ) … … (n-m)C(n+m,n)+C(n+m,n+1)+C(n+m,n+2)…… (n−m)C(n+m,n)+C(n+m,n+1)+C(n+m,n+2)……
最終得到： ( n − m ) C ( n + m , n ) + ∑ i = 0 i < m C ( n + m , i ) (n-m)C(n+m,n)+\sum_{i=0}^{i<m}C(n+m,i) (n−m)C(n+m,n)+∑i=0i<mC(n+m,i)
對于 n ≥ m n\geq m n≥m的情況，答案為： ( ∑ i = 0 i < m C ( n + m , i ) ) + ( n − m ) C ( n + m , n ) (\sum_{i=0}^{i<m} C(n+m,i))+(n-m)C(n+m,n) (∑i=0i<mC(n+m,i))+(n−m)C(n+m,n)
對于 n < m n<m n<m的情況，答案為： ∑ i = 0 i < n C ( n + m , i ) \sum_{i=0}^{i<n} C(n+m,i) ∑i=0i<nC(n+m,i)
變成組合數字首和的形式之後，設答案 f ( i , j ) = ∑ k = 0 k ≤ j C ( i , k ) f(i,j)=\sum_{k=0}^{k\leq j}C(i,k) f(i,j)=∑k=0k≤jC(i,k)
然後就可以O(1)轉移到相鄰位置：
f ( i + 1 , j ) = f ( i , j ) ∗ 2 − C ( i , j ) f(i+1,j)=f(i,j)*2-C(i,j) f(i+1,j)=f(i,j)∗2−C(i,j)
f ( i , j + 1 ) = f ( i , j ) + C ( i , j + 1 ) f(i,j+1)=f(i,j)+C(i,j+1) f(i,j+1)=f(i,j)+C(i,j+1)
然後就可以用莫隊算法， O ( N N ) O(N\sqrt N) O(NN
)算答案了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 250010
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll fac[MAXN],inv[MAXN],blo[MAXN];
int n,m,t;
ll ans[MAXN],ans2[MAXN];
struct node{
int x,y;
int id;
bool operator <(const node &a) const {
if(blo[x]!=blo[a.x])
return blo[x]<blo[a.x];
return y<a.y;
}
}que[MAXN];
ll ans1;
ll C(int x,int y){
return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
const ll inv2=(MOD+1ll)>>1ll;
void change(int &x,int &y,int adx,int ady){
if(adx==1){
ans1=(ans1+C(y,x+1))%MOD;
x++;
}
if(ady==1){
ans1=((ans1*2ll-C(y,x))%MOD+MOD)%MOD;
y++;
}
if(adx==-1){
ans1=(ans1-C(y,x)+MOD)%MOD;
x--;
}
if(ady==-1){
ans1=(ans1+C(y-1,x))%MOD*inv2%MOD;
y--;
}
}
void prepare(){
fac[0]=1;
for(int i=1;i<=250000;i++) fac[i]=fac[i-1]*i%MOD;
inv[0]=inv[1]=1;
for(int i=2;i<=250000;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=250000;i++) inv[i]=inv[i-1]*inv[i]%MOD;
int siz=700;
for(int i=1;i<=250000;i++)
blo[i]=i/siz+1;
}
ll fsp(ll x,int y){
ll res=1;
while(y){
if(y&1)
res=res*x%MOD;
x=x*x%MOD;
y>>=1;
}
return res;
}
int main(){
prepare();
int p;
SF("%d%d",&t,&p);
for(int i=1;i<=t;i++){
SF("%d%d",&n,&m);
que[i].x=min(n-1,m-1);
ans2[i]=fsp(C(n+m,n),MOD-2);
que[i].y=n+m;
if(n>m)
ans[i]+=(n-m)*C(n+m,n)%MOD;
que[i].id=i;
}
sort(que+1,que+1+t);
int l=0,r=0,now=0;
ans1=1;
while(++now<=t){
while(r<que[now].y)
change(l,r,0,1);
while(l<que[now].x)
change(l,r,1,0);
while(l>que[now].x)
change(l,r,-1,0);
while(r>que[now].y)
change(l,r,0,-1);
(ans[que[now].id]+=ans1)%=MOD;
}
for(int i=1;i<=t;i++)
PF("%lld\n",ans[i]*ans2[i]%MOD);
}