[2019牛客多校第二场][A. Eddy Walker]

题目链接：https://ac.nowcoder.com/acm/contest/882/A

题目大意：圆上有(n)个点，标号从(0)到(n-1)，初始一个人在点(0)，每次会等概率向左或向右移动一步，如果某一时刻所有点均被访问过则停止移动，问最终停留在(m)点的概率

题解：若(m eq 0)且(n eq 1)，则(ans=frac{1}{n-1})，具体证明如下

　　　若设答案为(f(n,m))，可以发现这个函数有如下性质：

　　　　1.函数是关于零点对称的，即(f(n,m)=f(n,n-m))

　　　　2.若(m eq 0,1,n-1)，则(f(n,m)=frac{f(n,m-1)+f(n,m+1)}{2})，画一下图就能知道为什么了

　　　接着考虑(n)的奇偶性，若(n)为奇数，则设(a=left lfloor frac{n}{2} ight floor,b=left lceil frac{n}{2} ight ceil,c=b+1)。可以发现由如上两条性质，有(f(n,a)=f(n,b))，且(f(n,b)=frac{f(n,a)+f(n,c)}{2})，因此可以得出(f(n,a)=f(n,b)=f(n,c))。以此类推则可以得出所有(f(n,m))相等，所以函数取值为(frac{1}{n-1})

　　　若(n)为偶数，则设(a=frac{n}{2}-1,b=frac{n}{2},c=frac{n}{2}+1)，可以得出(f(n,a)=f(n,c))，且(f(n,b)=frac{f(n,a)+f(n,c)}{2})，同样可以推出(f(n,a)=f(n,b)=f(n,c))，同理可证(f(n,m)=frac{1}{n-1}(m eq 0))

　　　注意对(n=1)的特判即可

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
LL T,n,m,ans=1ll;
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
int main()
{
    scanf("%lld",&T);
    while(T--)
      {
      LL res;
      scanf("%lld%lld",&n,&m);
      if(m==0)res=n>1?0:1;
      else res=qow(n-1,MOD-2);
      ans*=res,ans%=MOD;
      printf("%lld
",ans);
      }
    return 0;
}