题意：一个人从坐标0开始，有1/4的概率向左走一格，1/4的概率向右走一格，1/2的概率不动，给出步数n，和最终的位置m，求到m的概率为多少。该概率可表示为p/q，p,q互质，求出p*q的逆元即可。

思路：类似规律题？

先画下图：

可以找规律得到这是一个杨辉三角。

杨辉三角的第n行第m个数可表示为C(m-1,n-1)。

所以题目要求的就是C(m+n,2*n)/4^n。

那如何求4^n的逆元呢？根据费马小定理+逆元的定义，可知a关于m的逆元是。

所以4^n的逆元就是4^(n×MOD-2×n)。

组合数可以用卢卡斯定理，这里要注意m可能是负的，所以要取绝对值！

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
long long PowerMod(long long a,long long b,long long c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
        ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
long long C(long long n,long long m,long long p)
{
    if(m>n)return 0;
    long long ans = 1;
    for(int i=1;i<=m;i++)
    {
        long long a=(n+i-m)%p;
        long long b=i%p;
        ans=ans*(a*PowerMod(b,p-2,p)%p)%p;
    }
    return ans;
}
long long Lucas(long long n,long long m,long long p)
{
    if(m==0)return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
int main()
{
    int t;
    ll n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        if(n==0&&m==0)printf("1\n");
        else if(n==0)printf("0\n");
        else
        {
            if(m<0)m=-m;
            ll x=Lucas(n*2,m+n,MOD);
            ll y=PowerMod(4,(n*MOD-2*n),MOD);
            printf("%lld\n",(x*y)%MOD);
        }
    }
    return 0;
}