char C[10001],P[10001];
long long M=1000000007,S=4600000,c,p,l,r,y,z,a,b,e,j;
i(long long n){y=1;for(e=M-2;e;e/=2,n=n*n%M)if(e&1)y=y*n%M;}
f(n){
	if(n>M/2){
		f(M-1-n);i(z);z=n%2?y:M-y;
	}else{
		z=1;
		if(n%S>S/2){
			for(;n%S;)z=z*++n%M;i(z);
		}else{
			for(;n%S;)z=z*n--%M;y=z;
		}
		z=0;
		for(j=0;j<5;)z=z<<6|
"    !9)KE\"DUX8B>30# U[O$..MV)WVR>^QX>C$BJ'D\\72-I[-7PZUN=C?V(:E'$E-\"/-<P:>Z.6(0>0#WV?#W/MUVC%9GCZG_U6KYMS9R]T%E1Q.DFYHIM28MFJ;M[1.P<TP^Q 9^WZJ6HEY=]5M*)@IVNL7 /)(*0B3#W8Q:V%Z33B83\\Y$1I@ZB_88' V_;HV)7G11J+7U$00) Y6QO#,T[VG6<+/_Y*1\"@3TU5?\"ZPIDH%2GH,4T]W0!B>^6;#?JE$(@?<PFXADDX]FH:*OF34,L9@HM,^:O&%7$P:6[UCMNI(F\\\\KHY\"P8!E_\"VJ3Q76A80/G4'RNL'7VE \"!EP4X$#V%5I9,>::$'?L8W6ZIV^F1L+(,>E.DN(JTJ$PIT7?[G:=[;-O3PYZMS+JG _ML+;',_:IQ \\WFA&?S$J,#C7%/'GPM,Y+C1]^18/P<05]<2JUZ4.SAU<XR2V&TJND6D[#AI>Z[V[R/5:NU#0UDU(1EV\\09<==3L<S^M0\\0Z$4E:R.:>J$2 ';U4;#!]>3\\+[IS$B\\!K.KE"
		[n/S*5+j++]-32;
		z=z*y%M;
	}
}
main(t){
	for(scanf("%d",&t);t--;){
		scanf("%s%s",C,P);
		a=0;
		if(strlen(P)<11){
			p=atoll(P);
			c=0;
			for(j=0;C[j];++j)c=(c*10+C[j]-48)%(M*99);
			r=c+1-p;
			l=r-p;
			l<0?:l/M<r/M?:(f(r%M),a=z,f(l%M),i(z),a=a*y%M);
		}
		printf("%lld\n",a);
	}
}