import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static final int INTERVAL = 700000; static int dec(char[] a,int l,int r){int ret=0;for(int i=r-1;i>=l;i--)ret=ret*93+ord(a[i]);return ret;} static int[] decs(char[] a){int[] ret=new int[a.length/5];for(int i=0,j=0;j$KR^G'a_&e)Vv|5*Q)yP&qRZy#/:S?$mf!D'_lr**C{s}%r8H/+q9,Z(E~RI+U#$7#Q_It,$Hn8+WHN@'LQ2D,Zmox,EXGX,F=ke)P~DG'[r]](NP!;$K-$`'N#C<({NxU#1j50)]oy* O2<).o7Uw-;A%i$I0:1!R+/9 |P|z%[3=]'1(Tx#F^RD @EtF py~_-OiPd it>#*{nu6#ZWcR!i9@D!wJgs+]Ju[')Qr5 3C?P$V##P(BfId*z'3F+Jh.0,f ,c 9/q%'p*y2+hqbL++OBi){{BQ+Qw;K%a=V*%#k}P(.oZM'%:,m,33rZ hkH( GUEl-2Jmq+dB 3%5j9G(2d$o&N#+a*0EBU PB/_**u>|*1]bB)r^BN-1{-k%Uc:x!$QbK}']`.p#|PuA)/tTZ!p;fV'oHX`+5FR$ UGci)eT^K$2mw-(N'dv!fdI5,YnSk+`'Fa!z`rq,Xr$I,M_KT'O>|8#OiJ(*v-'r 'K:}+. %,! lCR#$M].+>J*~#h:V,.Z0Xd(b+Odxt#IwTu&:B!-(dS m(lnGG'5*!|!mR'/*W'GO*ZU6a!sN{/,C#4('[mf}&h{;f,x=aG(L M_#3E D~u])8tQg-SKHs&_{>z!JVvG$wD}K,Gx*y&QwZ$[,EM%]Z)d(Zq31+9(r<)M2v+)YT76*h5Ly(oxgJ('{0..Fo39)?kZV*71T&*2wpF%e=f)!y&3A)}xf8# vD**{nsg'pz68%5zz] SO0G* %(O+.HMR,;FZz)+8 Y-Sa>W e,p_'e*qA FK|:,>*7D!Q-En$!%/a%$> |$?Z$4)V?d'$nDZ$%Q#3n+vM{w !$%g!<~X5%Pqw$ m7s0)X3??&!vW9)@T&Y#AGNa ?zgo'Tr}R%sL]} yaI5,54Kz,F&z]$|(`}+eKE+& NP,.e]@a 0({a*3p<&#lW'k!y7R(*6>`2'%_b+';3iS)]n'p bWT}&N]ly!Pwx!'mv9B+6U[_+[U.4):Vq7!bRKd!];:I+,wnE+~P8T)X[Xf)iK*j+YSRo!xc(i#3~3O'O/O&*DTfX%u&Z7*>VzF)9ewf+{4*r-k&&?#O,@f#:y- %Oyn7$~>c2+Nz_&+-LL:#I&mE!UsHj%Tu[$=HI4&Qub^+%,4t)gOrx%(DbS!~ru4-5+DA q~Ba#vWY~ [Z,6,q6-j'T2nu'&@@% h;`-!M Z;,:Qe6+I]Yv+&IyBY&[T'p+<7Br){i+E-c5?t!N2pt-?a&;'^%2H)_vvC$7PGd&x`g>#gn_R*hCR@%U#&< b(7B O@6D#Thk?))q!n)3(;6*_;a9$AOA/'EG6/*!.lu!//_B&+0t5.|>R9%M-cL&u~PJ,-7ZA)31ap'wri8+QGuB$B.g^,lNPH*L-UM$--Pq%vqA $d{v: rjP@)]{g=,95vZ)Yqt.'$ZAY)=^GJ-$'M('>>bu$FLNo cm5J'/9'@&txI=%GTmD, Sn]%+1:S)o/fZ(gKH7.1'xI%GKdp,Z+i!=/*utqY%4yn5+xy_R!^fT#)JV^l&8T?p+6gql,L5en*).+D-M772+xB_Y,aoN6 p|bO(nJEQ+>m+,)dBi.#e_t=+au|>$2;IL,err|%gU%<(Ol-? x*T3-X}/B-cuqQ-Avg5$E)3U'51p(-Ys8j(lFw*#cvFx$Mu_f#^@OY&2=|4%GUGF @Ry?'0m+y#zbfL-}R6M)pcSa';ht Okf0%=_OK! z3a+bm)<%>a4n&GFE[ ,#^I$ 51w%}t&_$9ZKc!cpT'(]W/h&_/@' zK.n& ;=U*<]@6 VI;0%sf!$##o4D!ljWc =P!Z!s[(m&4(V(']JTP-#i;V-ED%~'~D~x'LnM{$[/|# qM{U#$LbO TZPX$69CW'9S;*%f#wO)VXLP$mGPQ&A*ab(iuYj#z[q,'P$~|+B!^Z#R%YY*{n6-*rptk%WGl=$pZ6%#Zj*a,yE.5*qb=@*}-sm*PM..*kp2;,c,?X'[I}d-Vs%S$W@9`-c6%0'uhmk#F2yG%(iYy,=E~F$;6nG)7_hF#2<|~!%fsZ-Rz'_+K R4-U+qp+T4~0,L5|U!76!:./X?Y-s.:i,/%&C(7Q4v&d#__#n0i]*p/K(+}%}8.,_1N!<$kk(S-{ +Dskf,Iw/$'6/+y&z-fj&y dk#2a&f B,f[%nin;(6UZX%QMaQ';p{z, (J:,Wq|@*,9,b-iM4k+ NG;-xeI/!e'4;#a:S~&E5g}'1Kz(-t%2B%$B0Q *W^X)FuE('e5+_'ku$<)g1#<-?5Gf$t@V)+&0<,,'-Y[+fR`_ %P3C*RU4k*PwmR $J ^(AkaK+9_Bj(gA:F)}P-[,};u` ZD{?)IMZ7%YPpW'/k$u'O(wi+h(yw#Jf}m-S*.A'G9me%TaM$%jBPd-($uj+BPPm#zNCT+@R*$$#=+D'i3Q<%[t+3 :8f.'?(NF*e:iA*JT=m--$5k&g`cT&Rav%%4Q*9&:N1c%'&qe+>K^|!e2DP(#Dj{(b.&t+sp/a { {f$-Q/g'*&uY$H0ai(Z.Jr#pc~M!0>a5 ?Q*+!aYLX'%'l:$/0o4%]8ug+C&kL'fkpP hEPL#UhXI!WsS1)?bHI)UBk%)T1{X idm(-~R}r#K]S;#xD8Z->hXj(>F$f(V&9Y*&*Jc&6;'C$346-'.$bP$Afo/!5W;8()(d)(<#rO)oujX+J74[ v%;9'9{@J+PpUx*L!(:!Ym~7,8A4&.3I!h$u;Ly#|A@H!jFGP)UE#w'N#4F#lCd*)duuH(i9qV$>#6w!V1t,'jROK M.@q%0`*.#Jno((xCqt%B~jP&H!['$,.!|,!>c -%'3O $Rn;*&>lH&99~T((sGa-2XI^&}U}h&#!5D*=M[?.,!OU+3a}J-1;[}!S*.&**333#0ZT*);NBc'mCfF)SD_~'l#Jg(Jbd$ ~uF|%&(6V(~$-z,3m*R)q9Wd$up,<.7p}=*@o.>)a_u)zc(%$U8Lg%(n=r#Mz`E#D[Q;-0|ex,K0cF) $Q+!%,mI)+#R'#%|_T Q/PZ!HOJk(WP;5+R]{m,/79V'6z0d)Rfi[*HJP@.&;^?,GrWK-- ?f%lhZ,!C!Qh#5gDP#PS6G%k@ B*y=?Y#m@)S*XM~S%~N&.a+~!Z4'D*d`;8)=!e&%LTWD%:6=H#,O;&(N.Ig!>d?=!Nzn7'@cou'u[25'Z^nP&r!!7 q#.b%_ZkH c// .#oFi-b)w&%7llK!6@Cu)`e?^ ~Ok[%&o;e(>yiM%Rb4+$[,^#.7A@!)f^b_!YG6m nX'Z'd$vn$bjd#!GYCy%V|2**(I^Q&&5xG$SBos ]c@j'k>T#'&m2m#,J**'r+W)%D$!G%bub 'J<.I!GhU<'B&g],,f4D 6Xt`&f[lY-<3i##dF0,(U6>a,O#W-D-UG cPC#-8w:3&U_eI+&jr<+e&M%!sHy0!dg>$,X79q Q.4b 8CXl)bZ_2'R(L_(EFo9./&/J-*1Y!*9zZ7$egGT*zT)*%Z?n]%133/&q*cY&L5:>!CA_R$MvPM,{('L+f(W~;V-Ax@E#:}6u v5Dr#5R?I$I.L$+JQX:-mD>X'Hm6Y''vID(opM+.&Obu+&YH !q7U&!GSi_+bfe}(Ub1~,pCfR-f.=Y'(xrz$t&uv&& (_* *~K)|w|&*{&1_-^&II$o0A='T~tw!s3hU+@QX} 3+Cb J=;4$1.(EHS-Q4_j!V,Nz&u1TZ*Ty_z#bI#(.sY!,zT/.K0;%,pH$Y#*cg&$)(=`!)/~<)DYs>#b%kU!f68Z#,*Hj(>!s?)g3,})JPt$.p'#Q,1Fd:&!'%o%YKjZ%=xc0(zM9;(wD8Z!c|%w*bdN(,(U*/#is:;*YaB'.VgOf&+^}{)m-_q%pLSe&{AFG'{N{',csy{,c(P..(`AW'>1ci&x'Z.+n2J ZUPE'dr~/+l]XW&*>)Fo V_*_([!#%&NxEB%YNm&)BP-j&71Hd!{,/v!2TG} 3T81#$qy`!ZnR($%yWt+o#3I'xdh9'XD6U(f;L>)@xi%&DDuO);9V]&]Bbh,'`vE!|*B'*ORWh(xo7X*cS(i&|/3/#_@3w#SV%**w#Zm!gu1~)<|-p+DcM5,DG]n(3.zT$X&9; yV?)+Y0'S$!ged#,tIt+nO?I+t05u'h:Ii)r~w>'1imC-7$f-%5.9~%C^}9'm~0!'o%7m (eLG Ns;w!.4e}&rBZ6&Dgh6+R0O2%Kl.R'.+M=+sOqF+zn%9,XvMS,?pyt!'|D(+7tpV$Gg*L+xmu_ xeqL)4~&).KS9F$'|2#+.4_;)L~-q-|w*<)+j;6*!,c')=jQ#'uH|w)5QH>.v4X/!`M$B+Ye9-,rTMf'!NoG$*+X]+G~mF*|$/_#p-Hl&&I6A%}*f:(a.;9&|:x+&-<=3,?THR UKF!+(@i!+HR#Z$*tkA%bRM%'4Lda+V'ca+0Eq=)-Us4.sL!P$$rwd!k'<.,9hAD$wR*C(qjp%.~H+^$74R,)3v?d*GpdV tNW| H5v4 DQ0c)NAQ})1)l$.a!6b*/)hY!@T V'4?&e#2C]`*0vqf&NUaU,rC$N'BS^R (@Bq$JNsw%t9 + 2g54+@q>)%paqL,)Nr;,Z51B#Ctn-&L.K* ha W(,3C5&TkI<$Dv|<#a,p& On]D%2Y=8.'Ahf,`K~'-OFn&+89w1,Vs:&,;-he-#:_r-jcLn((fL'$s3&u+ty9K%(9a<*gj6T*H6hw-)Z_) 79tB#uF9Y+wuh8(7F5<'xU)--wDkQ!VN`S-Wduo MnDo#pCzu%`CCt+oNq'F,i[,R1>D%1syz'b|jT'W>7i(]e,r+YL5u#?pB[$%T2+ c]T)*7~a&*b>Ui#+*0),X)0V0_%*ZnQ(dG=H)){ze)Au*%&TwZw-fgD.%]C $z+;$;h}b#~kFB(Cu@+*6ywl,.O~j$t0%h#5Lo~$Wa9{,FV2~((&|_*lP8e!dR<|,cBdn fH~t(".toCharArray()); static void solve() { for(int T = ni();T >= 1;T--){ char[] C = ns().toCharArray(); char[] P = ns().toCharArray(); if(P.length >= 11){ out.println(0); continue; } long pl = Long.parseLong(new String(P)); if(pl >= mod){ out.println(0); continue; } long cl = 0; if(C.length >= 12){ for(char x : C)cl = (cl*10+x-'0')%mod; }else{ cl = Long.parseLong(new String(C)); if(cl-(2*pl-1)+1 <= 0){ out.println(0); continue; } } long sup = (cl-(pl-1))%mod; long inf = (cl-(2*pl-1))%mod; if(inf < 0)inf += mod; if(sup < 0)sup += mod; if(sup < inf){ out.println(0); continue; } out.println(f((int)sup)*invl(f((int)inf), mod)%mod); } } public static long invl(long a, long mod) { long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p < 0 ? p + mod : p; } static long f(int n) { long mul = fs[n/INTERVAL]; int base = n/INTERVAL*INTERVAL; for(int i = base+1;i <= n;i++){ mul = mul * i % mod; } return mul; } static int mod = 1000000007; public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }