//from xjoi
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000010
#define mod 1000000007
using namespace std;
const int iv2=(mod+1)/2;
int ksm(int a,int b=mod-2)
{
	int r=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) r=1ll*r*a%mod;
	return r;
}
int fac[N],inv[N];
int p[N/10],phi[N],pt;bool pr[N];
void init(int n=N-10)
{
	for(int i=fac[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n]);
	for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!pr[i]) p[++pt]=i,phi[i]=i-1;
		for(int j=1;j<=pt && i*p[j]<=n;j++)
		{
			pr[i*p[j]]=true;
			if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
}
int C(int x,int y){return x<y || x<0 || y<0?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
void Add(int &x,int y){x=add(x,y);}
int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
void Dec(int &x,int y){x=dec(x,y);}
int n,m;
int solve(int d){return 1ll*C(n/d-1,m/d-1)*phi[d]%mod;}
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int f[N];
int main()
{
	init();
	int t;scanf("%*d%d",&t);
	while(t --> 0)
	{
		scanf("%d%d",&n,&m);
		int g=gcd(n,m),r1=0,r2=0;
		for(int d=1;d*d<=g;d++) if(g%d==0){Add(r1,solve(d));if(d*d!=g) Add(r1,solve(g/d));}
		if(m&1) Add(r1,1ll*C((n-1)/2,m/2)*m%mod);
		else
		{
			if(!(n&1))
			{
				Add(r1,1ll*C(n/2-1,m/2-1)*(m/2)%mod);
				Add(r1,1ll*C(n/2,m/2)*(m/2)%mod);
				Add(r1,1ll*C(n/2-1,m/2)*(m/2)%mod);
			}
			else Add(r1,1ll*C(n/2,m/2)*m%mod);
		}
		r1=1ll*r1*ksm(2*m)%mod;
		int p=n/2;
		r2=C(p,m-1);
		if(m&1) Add(r2,C(p/2,m/2));
		else if(p&1) Add(r2,add(C(p/2+1,m/2),C(p/2,m/2)));
		else Add(r2,2ll*C(p/2,m/2)%mod);
		r2=1ll*r2*ksm(2)%mod;
//		cerr<<r1<<" "<<r2<<endl;
		printf("%d\n",dec(r1,r2));
	}
	return 0;
}