Eddy likes to walk around. Especially, he likes to walk in a loop called "Infinite loop". But, actually, it's just a loop with finite length(Anyway, the name doesn't matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts N marks on the "Infinite loop" labeled with 0,1,…,N−10,1,…,N−1, where i and i+1 are a step away each other, so as 0 and N-1. After that, Eddy stands on the mark labeled 0 and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled i, he will on the mark labeled i+1 if move forward or i-1 if move backward. If Eddy is on the mark labeled N-1 and moves forward, he will stand on the mark labeled 0. If Eddy is on the mark labeled 0 and moves backward, he will stand on the mark labeled N-1.

Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.

You, somehow, notice the weird convention Eddy is doing. And, you record T scenarios that Eddy walks around. For i-th scenario, you record two numbers NiNi, MiMi, where NiNi tells that in the i-th scenario, Eddy can walk through the loop a cycle in exactly NiNi steps(Yes! Eddy can walk in different fixed length for different day.). While MiMi tells that you found that in the i-th scenario, after Eddy stands on the mark labeled MiMi, he reached all the marks.

However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen. Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.

输入描述: 

The first line of input contains an integers T.
Following T lines each contains two space-separated integers Ni and Mi. 1≤T≤1021 0≤Mi<Ni≤109

输出描述: 

Output T lines each contains an integer representing the probability that first i scenarios will happen sequentially.
you should output the number module 109+7(1000000007).
Suppose the probability is PQPQ, the desired output will be P×Q−1mod109+7
题意：t行，每行给出n，m。n代表环的大小（即环上有n个点，标号为0,1,....,n-1）。从0开始走，把n个点都走一遍结束。问在m点结束的概率是多少。输出前i个概率的积。（好吧题意我百度的，我看不懂emmm）
这题我不会推结论，奈何我会打表（好像上一场的F也是让程序自己跑结论来着），打表代码如下： 
#include<bits/stdc++.h>
using namespace std;
int t,now,n,x;
int vis[105],book[105];
int main(){
    cin>>n;
    srand((unsigned int)(time(NULL)));
    for(int i=1;i<=100000;i++){
        memset(vis,0,sizeof(vis));
        vis[0] = 1;
        now = 0;
        t = 1;
        while(t<n){
            x=rand()%2?1:-1;
            now+=x;
            now=(now+n)% n;
            if(!vis[now]){
                vis[now]=1;
                t++;
            }
            if(t==n)
                book[now]++;
        }
    }
    for(int i=0;i<n;i++)
        cout<<book[i]<<' ';
    cout<<endl;
}
跑出来发现每个点的概率是差不多的，由于随机数有误差，我们可以考虑每个点的概率就是1/(n-1)，（0除外）；
然后就可以愉快的求概率啦，（如果不会浮点数取模的请百度）；
下面贴代码： 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3fffffff
#define maxn 100005
#define mod 1000000007
ll poww(ll a,ll b){     ll res=1;     while(b){         if(b&1)
            res=(res*a)%mod;         a=(a*a)%mod;         b>>=1;     }     return res;
}
int n,m,k,t;
int main(){
    scanf("%d",&t);
    ll ans=1;
    while(t--){
        scanf("%d%d",&n,&m);
        ll res;         if(n==1)             res=1;         else{             if(m==0)
                res=0;             else res=poww(n-1,mod-2);         }         ans=(ans*res)%mod;         printf("%lld\n",ans);
    }
}