伦神爱散步

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 17:58   时间限制: 1000ms   内存限制: 256M

伦神最喜欢散步了,每天晚上他都要在学校散步。假设他所在的路是一个从$-\infty$到$+\infty$的无限长的坐标轴,如下图:

walk.png

起初,伦神位于坐标原点。每一秒他会等概率地向左(从$y$走到$y-1$)或向右(从$y$走到$y+1$)走一步。CSL想知道,在$m$秒后伦神的坐标位于$n$的概率是多少?

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,输入两个整数$n,m$,如题目所述。
$T \leq 10 ^ {5}$
$0 \le |n| \le 2 \times 10 ^ {5}$
$0 \le m \le 2 \times 10 ^ {5}$

对于每组测试数据,在一行内输出答案$z$,表示概率对$10^9 + 7$取模的结果。
严格地说,如果$z=p/q$,那么$z \times q \equiv p \pmod {10 ^ 9 + 7}$,且$0 \le z \le 10 ^ 9 + 6$。

复制
3
0 0
1 1
-3 3
1
500000004
125000001

对于第二个样例,CSL想知道伦神在$1$秒后坐标为$1$的概率。概率为$1/2$,所以答案为$500000004$,因为$500000004 \times 2 \equiv 1 \pmod{10 ^ 9 + 7}$。

math

ACM集训队暑期集训热身赛