結果

問題 No.148 試験監督(3)
ユーザー LayCurseLayCurse
提出日時 2015-02-08 23:15:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 49 ms / 1,000 ms
コード長 15,129 bytes
コンパイル時間 1,639 ms
コンパイル使用メモリ 147,300 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-05 11:19:22
合計ジャッジ時間 2,657 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
4,380 KB
testcase_01 AC 18 ms
4,376 KB
testcase_02 AC 45 ms
4,376 KB
testcase_03 AC 49 ms
4,380 KB
testcase_04 AC 45 ms
4,376 KB
testcase_05 AC 39 ms
4,376 KB
testcase_06 AC 33 ms
4,380 KB
testcase_07 AC 41 ms
4,380 KB
testcase_08 AC 46 ms
4,376 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 5 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[77000000]; void *mem = memarr;
#define MD 1000000007

int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}

ll fact[200000];
const char *fact_str = "QD89O~%'*86Q$*)L.[$G')Mj<F0,Z#/L-l&9@5Mn#-IC&s/.=;`&C;.1_#.4+Dc#:>DDz%,&H8e%2(%Ek#8#ONb#,(8$S%5/36s&DLF3Y#J.3Ky%05F#[%0(/#S@%%C_$%<*Jh75>@^A7I:`&:42;]#K2H=ZG3'=t%=*M-|$KD$4o#5,%C^#?$<J^%M$.>}#+;:)s&133,o%#L61c<79FT#4985k#NHJ:`$3A57c%-2-CP#*F<&o$C)!EZ$D2:/z&5N-=]#+(<&h%@O2>q+MMY#F*+R$HMO1q#=-N?j%&>@#P$5*H(i&.LF,g$;>C9m&1<HU$C+9/]&'ME?Z&6@6>o3%C?k%;8E0X#/J>Cv(G%>R&&'+(e&.*,)w&/M9@X2:+2m$240Hw%D,=-T$-=5:|2+#9_$?9@BQ#/&G@`&2=B6h$.;/)Z%J61KV#D0?O{49N.]/1N@c%9@.,u#;=H6wDN(IP#2(3Is%9-<#P#%><:^#6FBF{%MK0-i#<.>-n#D3H8xH=<7f##B2J|#M$'8w&EE$Ev$<7$7y%!71/x#5F9&r#%;B%v%MDF,Z%/#9:u1#KKt$B9.Aq$5&M.W$43B?fMJ,M`%:/DBq%9.)E`$'-'Ca#&OJ1V$F/91n#O$F,l$H29:e%B/8!b#@9+=l%>CA@nGB)Y%M.GBl#+F)8_%ELJ5T#8;+Ed(')OY$.3F&h$'KAN{+N<._/.NAk$50GAy#13<U$$CGu%C'@?]%/II-d$M5)CsBK3Kx51FDz$'3.'o&0C#'Y$MBFMS#@(C7z&0%)I_#FL-.}N,EEy%#B?K{$;D;6T%H*B'i%>%,IU%L;36g$LI>8|&H@3Ei#O6-N|$HB;-U#8A98g3)$m###@%X#DFJFz$/&O=`$13$Et$A$8>P$JL0Kw&3221U&$O6.e%:5.,bN?=7RJ.#>{$;@-As&2M4)w$G7<(c%E'>?lB7H6n#M>N(u$,;;@`$A8?7X$=3+3e%-7A*{$(+?Gi$6C);f&%AOCh%#<$Mo&2I&Nw$B4!3a#(A)JW&(!GDh&01;Bh&$4&9r%*:D%TMLM1|%<9&$v&):+2|$(7B'Z0&CJk5+64r%L/##t&/979_?9/Fw.<7-s&C8(#s&C5,'}#06&4RGC(:V#$=?@f%KD0Kd%',AOU&9,DHoE-,+u&-BG6tL/$Of&:EO;z#GCN5r%/%*.S(HN.R$DB#>j%12/Gs;%+JU%%%@Gu,#=:S&?/(+p*FN8[&D-'Ak,<O4^%LGO6c:/NNu#+L(2_#2MEBg#OD5<P/6(G{AK8HX%2ALGT#.2C%x$&@+%}NI!=V%*-=m$OA%'S%D&!!aI!#DQ#M49At$G=LMl%3A64r8I&5`$$+G$s#&O(3d#%)1&c#>?O>c%+A,*Q%M2/:R#.7?N~#C=M(xG<%8o&$;L:[%K)B.Y#:=O@s$?9;/X&-K0;]&:HC?j$FD;Kb$H59._&/A5:c##/?6P%.'(3m%?EL3aM&C1p&C*3Fw>%$<Z%#-ONw#DN(NX#>I1/Z&8<O.f#*11E`5$<3X$AK0Nw$'B+'Z/4M.u%;L/Bs%J*HKp%'G>Ex#L5.9u$'..CvH97IT$$4H$kE?,$s%M6-Gu&0+%Bc$*0ONV&B@$1r#%@/-h#+L5*~%2%0+T$2O;1z%?(4Kk&),M4z(?N.U419LW$?52@^#'J&<T?>&CP$8@)/p$)&;?w#*9K=`&?;1(z2#'hM'M<p%3/E4e*$/;]#.338p&>NHMT&'>7$[$L%'(g#<*=At%B352U%>O.6`#JD>$}$)*6Hz#L<@Ab%+,@C}&G9GNg4#4&k#'DN.b$E02*i'5@%[%,9K't%*#-3Y&!EL?X#C)#QMD9(b(J;Of$FGI&^&=<03~$,.(DT@C)#m%;3CIv&H.I8[##;@;[$J@7.|$7B/@`$0N.<P&!GM*Z$L8F4T%/8I+g$4K.9[%/2=4[#J2=M_#4BGI^$,$D0^0H+OP#!<>EX$B)JFx%0$/8~M>2-V#E8O3R7AM>v#5D0>x#B%*4i#4G3Ab%G2!;f#6:1(w4?D.v%'O(@r0F=Eb@.&'~-?MAb$52*2x#8@#Fp$5<G)V$@0;.}&:/M;ZAMG>Y$5>3Nv#B)N1y;6,;m&6K'Gw$40,=v#6)EH~53!#t&H7I4r%LDK3a'(6Dy&$@F+P$L8*Hw%-GG;Z%?*:G]%%')1YKHE#U#I8-)_::6<x7+!Df$F+?FX&C9*Ji9<?6h%?OG:}#7LO2s4=?6|$?(ELt$=LANn)BHAw#32L?a#<C8;r#*18Kp$'F.*k#9FK1W%$HG+W%07?@T'OJEr$N935b&:5J2n&1I&He$O@36VN2A![#)3':b$K&B1`$8+A#y%0@M>q$B7;$z#,=?.s&5;5?j#+$,$i&'=J't#0JN*X&@*4&P#<?J-c&8>C4x$4D04b&6,H>w&%I/2{%9I-K~$);'<Q%&,78h%MO7<U#)*#8gH!NIs&=12$X$,):?W&50$A]$KHIEq;A1$`%N-@V$3M&0^M84%o$*=(6z$/32/o&$7&D^&#AEHs%B5!(i872(P#F4,?_>?B@w$0.2)a&6O>+|%=4?=u-:%2s,$M*g&H$HCn%L#%He$068=W$-CA;}&$;$>eH6-Mx$?F?0[2GA?}#@HB&n;N6,n&=.%7~$C?(Jg#2K>F^#0#N8s%%ON$|HG4Nh#-AB+V#*4L3s%95K=u/D;:m%24./y$1<6*t%@&%>j&;;83q#I*%)]7-J3u&/A3Bv61=Jb%A7N&e;EM;s$ON6,z$4;B8f%'.*;l@38Ct$=NA$Z$7'=-Z&HA0#d%6CG=RK208X;2F#k6/<EP#EH'@Q%FNN4f$D()+b2G3$z#0229aO58!j#1K#0y%&F*)^3H=Aa#EM:.T%4N58n$H+3$n;&@Fr#*F%/r%;'/Ox#??K$h9!E?X4KFj%/5#8g#K1$A`#?G;9TB5-NwG2*(^$+BC8|:*E,gD?9(y&%46>j$M*?Co$1$:;}$>BC$t#0B.As$I,N3k@.$Oo&*3I/s#2#*8l&;:2Ne$J!-<b;G5Id%M.9>v%$85G^#BL&Ar$-<.2Z&0?:0P$1:$<x&%<2)e#6.@?ZLN&3[J:'%{%<6)<`(F?$[#:@OK]&&;B1P#$<O2|#EEC9d%H##=l4940U%!,3*W%2I#*zJJ+2W/;M7]#I$GB[$$'M!d&H7=Cp#!.6,]&2A7Gx&BDL8z#>K0Bm%B%JGw.%5=i#J&&!^$N9G1W&!1J$_$#@4Lk$C+49T&A>:/h9<I3|EGJLa#!-C(zCF>!Z&A2J5T&G04*Z&'M!4]$MC?4t%J7CDt$*@:If$:<KEoHDJMc*E;Bi%(M:BQ#&@4,a&BI'1m#@2E2v$5HIEoID*(|%F,D'p##,I*r*C+Ea#F3D)}#1HC3x#1C>Jn$,GCBw&7=1Dx%)5!.V##0:Cu$-$63m&(9NGi#D'*2`%$1A2R%'D;'|O/=0R$C%1*SK>#?R%-,&2f$H1*%U%12IEv8K9,P%.4N<b#LDM,S&?J5I|#4IG<jN?2Ar#/0?My$CH:1T%G5+Bz&&!3N{%).;7n#J$E*z$633Ki$6EH+q#B@++i&?%C>Q#!C1CQ>B#Ix&%4*5V%1(D3t&8'A0V#6G=El$-E=HV%82-Bb$$BCDh$G$!!~/?,.c#;,G6]#D*4EZ%DAA;v&#D#4o#8:/NP/1;#iO?86|%C1B9x$F&KEm#ICC!X(L-8T%AH)/]$*=-;RIB$:w#E''Aa#C/$O[#-B95w2B+,t$/>F9p&*6ML`6O''j%($C&Y$I(L7v47>4a%E3&=e&D0OBY%I)G6i%H(+8i#5)*.i.83Lg$:=33S%,$BGg$G:AHn%C'(Be#>KN1~&(+C0kAL<Iz#*>C#}$/50+P&FN,=R$C$C1t<4!E_#>*/C_&%CH3P$5:69s&648!l$-E(GZ$HH'3cFF>/Q/AM9o#9#)Mj$O3)+y5,D%g#*#9Oo$G<HMl%H=<#P$CL'7i$-!!)m&?-CAp$'+*NY%#8BK{#&8*2t&2#,&a$-1)Nx&03O?T%+>;O~&$K)4u#0)EHw&8GG=Y%-CGNU#J+L@qODO5oK*@HQ$:/8*p%9D.(j&1G7$U#N%KO]%:-7Oz%7D,7P%<C):Z%8(&B{&<A0AS&#8OJe$=11Ls#I>G9~#LL51W1.G=r#/8>CX#9*6r#,--.PL.*8P#A#N<m1-L9i%#29Jm&<DFL^%3IA:U#N>=HZ%,?H;P%M(:HX&$-%@qJ&04Z&&<3GW&!/)5t%*:(3n#@F)Jp&+N!%b&F!6Mq$F8L,o&+O-/j&<<-*RC)M&~%%421vEJGDQ&@@25U&/!L8f&'842e$J+)6e$O;7-X%4@6(b$?G+5f$<0-1[$10-5t#787G}#09>*a&CCA8s$3!!*`#)I$Ji%=3NI{%J4LMr%NL.2b&<%&>S&-HH!Q$=9@|#5?>C~#<@3;q#?70/j#A/?8^-=4$o;DA>e<F6!g$/FHDd%=NGG~#$BO@~&8M?=^&.+(IX$;#:KtJ+//g)2-y%4.KAi#JJ?)Z&6GH@e$-M,Fo&)3'!W#72D<z$',5.X$8I-OS%L=H3U%JO#3U$$)?'m#I:#6g9;$+_>76JU/3,'Q;8KEg#<#(.U&3+>%W3FO&`%G;G&V%7DMNh%0<7MX$%J.-q07'=~#LKC>]%6JC!Q#:A83T-F!5t#IME(z&'B@>V&<!D1~$7F@/}&;2?Lq8L10[&<$@5k%GL7&}&=>H/q%-0>Bh&$)?7~%OA)=Q$J;A>wLLBKu&H8/&[&@GL;o&F92Gg&B$JCt%3G$/x#L,%7W%&%JNj2'5NT#1,N4w#?@>!l$#7L8P$-;OKr&8@CL~$,3'O]&>G&@l%6(>q&1=LLW&F<$.U/'EY#'8E8`#D&BJz=A42]AA8JQ&&:@Mq$GM;1b$)F<+P&F<.=`%3O6Ll#A96HS%)=KBP%E)-;p#:LN=Z=OI-v:D?@t&>9H7v&>?H8e#+04Bl.G&)~#@>0Cp%D%I,T$DM85l#=GJ#~&HED5g%0H!LT#!CBEa%6I/C~#HNM!{D%L>^C4G.|#?@'0e#KCK;u52<.l#9#MHc#!M:>t&G.N9m&$?LFT#.D:0v$<:D3[#<@A!U#&M#$]%F,,0Z$?-**z$A%&/c%%H%8V&G/60X&E2,6Z&G&3Jn&:MJKwDD.E^&G8O6w$K.B.P'@LEl%6L.IZ$87(#U#0$#.`;,%2y$*G.5Z&<I4*X#HCJ:_$(0!0q$-1!K_%-5'#{&@G2Ng#A36Cu%*+.Kh#7.+?}#I8:.R##+G'r+1=CkJNK:f&&2#%w#MB4Ha%.G45S?H3#o&&I.)Y&$G'C]&:@:!Y5/H8i%=9NOS7#*0l#162'W#K07(S%,FGDv$,3H/Q#<F0CR&951<n$;905{$<58+j#,4?/|$697Eq$&8;4f%!9@JZ$AM$0l%B3#FS%NB-LW$L-78]%@8&?v%O6&FX%I=:ET%=&'=x&5$M?r$KF?&[#2-1&[&3J;)f%8B=Er$EC:Jd%$3)Dd%)8(9|$$L+E~&<6!LT#;HK1c#+JJ9o-/D;q#4(,!P&#H5@PH=D5gN4%Mk#=AA!q%4F*.c%KO:Ft8)(>_MC(@u%6!0Nr#96-Lr%>L>Nw%ID7;Z#76ICl#IO7Go$5$$+P$9*>7P#'47z&41BCR%:2MEn#&A+JS#I6K+f&4>JDv#6)2K^I7.7SK%+EY$&):Kg%5&8@u%,%$-o$A06H`$J@J>o%;A.'Q@O56X#B*E5b#7BA2e'G6'z&A&/N_&*FE3}##8IOs#$3N'k%A.0<}$C7++t&1B1N[#BH$FZ#0/0@P%G(!6z#K#NEg%;F#IU$6@?5[$62DDZ%MMK)l$,B?Md83%6d%K3B)[4FKCa%BK4t%#B-!lJ48Ay%N+G0z11O7p$::/Ca&F'AFP%K>I%_#N.A?w%#C-<d%?66)c&3M=?n7I%:S&9-7Ou$N>M6j#?%.Fq(MH?Y$40)+q%,!FOcHK%&[&+#GIh##N.Nw&+)4.j%0:DM|G8-/t#D@;)R$BK+(R#:B23Q%87?-Y?!4.^64:*`#.:./P$MNILv(EBNi$/C2.a53'DX#J%27w4OF=iD!1Km&/2><Z%0.)3x&60*=],7!-R$5?%Of#9M#/l#7(GHr.>MOW%)A0:R$(K(6y&%KH)k%IL*JRK>CK[#-+:%~#3<70VCMK$|;J5y%&*!:c%,;IEj#J%-=b;G+1}$A9B$g%5KH#d$3D?KU#/F=7P&7012Z%D4*-b&H7&KPO=H*t#<N.BV$;&*;uEE1<Y&&@J_AA&6z$>O(Ej$>F+&Y$)3!3x%2HG,q&1M>2s$J?M2_#.3J3WK@H'k$;/L$f%1H>7y&?J+'t$D/1!_&E*+Ld%?2#AW#+'?0h$:!'NP%%3<;g$A%FA}&HAM+t%3<M@}$/DG1f%E&2Lz#12B9e#FFF3U%0G0=~FA5%d&72N=m&65(Kh&8>30S$,)K8R$J)B'g&8)%(e$G59NY&5E4&}%*FC-k%ECL2e$G;I:w$-@+5x%!/E;|%&7OKf&-<-1[&?B6Bw#K/:Ll$3=$E_#N2$=d$+**3mLFMEi$-/J5l%%.Nb$6*6?y%$:4.w%J5=I|%#1))S868=y301(V%4/+*R$#&/*i&'H34v%==4;^%M-J6U%>I;5b$(#@An#+6.5f$M:G!^))9Mt&4C?/e&I/I.TJ!(3R%EGJLs,CA7w&ADM*b$775NV$&J=-u%M1@Dz%$O5AP%@%79i%=*9>V#M?A$~%#)!&x&'==(l%;-!Gb%BBJCd$M'H@V)CE9X&1EOHm$<155d;)4IZ$'21LW&HI,-r'G,Fe.;>,]#!8GDWN,0Ec$)BN@_%./+/}#!%EEbJ6-2s#ED9Be$6B!&i?5F.q##@O3SK7.HV%72@+t%(J@7TKF9.m$/<O3{$)H).o$:N/Cb#85,N}#0<+>Y#37%LU'=6=m&BJ2(s&)LK-f#,N+Mx%NA(Jd@;MKa#=I>Fv%=JM*U%9FL:d%;%BJo$'CGE[&+*9Lr%4@9:s?E)G_%#N(=Y$7K!W#2G.DjA?2+]$8$.2V$;K2*S$K0J5Q%;/<C{#6$+1~$O%./}#7ABF}$8H.EP$-IODP$!CEAY#0LG7z%0F*Hw$>1)N^$G72>p,K>$X&C,&(_&>7)!Y#$9+/e&;L(.e&?G6*x$D!/KV$.HG,t,H;6t<C,<mNN)Nc#/&GHw$2+*'p#?1C7P&*744c&C@B/V#<HI;t%DM/4XJ;?HW#4)=Nl%-/)Hr&*-4+k#3M%OR$.3;$S&A@I-v$E4B>[+I6$i&;>8>y#D4'Ew#-'-K_&;&:9v$HNA2W#O&O>^$G#>E}#/A$Bu:B;F`$+J2Go%?(;+Y$,:GJ_$4LHN}=J+'h%EM,$l#.=!Lv$/*N,Y&7:31f&.N6=i%N6J<n1LOAt$2%AGm&/H)<`CKK>m%3E&FdG0=H_#AGO<V$384)U#0;+@f&3EM,_%34K0x#DDFJUA,E/V#F+K.W$N99M}#?FC%o#)DG,}#JGA)c%GJ82z#$BE-V%(<!MP#+?C0|#70K/`&5'8Ke&!3+Ky#<'7.i%72!6xO-N0P#:CA7^6=G&_%!09?l$EO=/n#/15Lh%7N?Q#=FA;d7%('S3M!:w%>+-9e%7=>?TMI*Aq&?C4%k#>@E(~%*=DAk$&CLd8%GDs7N5$k#+AH;b&/!?Ay$N#LJr%CL?9Q(%84~#'G3=s#@.JIy&02:Ea$CJ*2Q@CB#d$K:9@s$H'C@aHA%&|#O!BJi$;0-%f&71H+d)>*)o&5',Nn$,B%/R&F3(2s$G*:J{#90'$s%1EK<W#G7D)e$%07No#.J>3^)3.<f#-2H;T#$5C<p&-C@,[%0.2Ds%4N=&wD!6:hBHDAt$A0:Os#8H+GZ&15GFTI+%7b$<G5<[J.I>h&(A*$n%J)B)P&5@K7d$M41CU%<$%Gw#IJC/YOO1(z#1(#Fk#6%NGs$HNMDx#6@G9[%02=?e#K6$I`%,I2%b%CK&%d&=7GC~%F(AO~%NM1)x$&',Hi$6++5Y$D+=<{#.948Y26LHz&!6DAP$(..:S>1O:|$=NE6R%4A$?`&8!@!V#:/9Oo#>%$H{#@11CX&GN/<x$C/@2j#9.E?^%N'G@h$#F)/q,66DPD2$=n,O1;P&D>(7xL!!JS#'-K(Y&?M<-a&D$J2y07J=T)G*By&:7,4V%&G-&|#=@??P&;:O?V#?9DA~%9<D+r%BK=,[#G<L+W&,,01_&!5M6|&D6K(s%7(A/v%%/53b&H<?9Q&CG<Fn$/49W$'2)HZ#93:<^#3!(!x#(80N`>MA@U?/%>S%A1O(U=2/BT&!IE4o9-KOcNN8Iu%%+2@l&7(9N{$*.J}#;M'/s%+?E3Z$@20I]#2&(5Q&F'+#j$-2,:{&(20*l%>O?CY$J7,1f)&%-|%1L9O]#7<=FW$B(;=p#O'<@u$D?:+x&/5,7y$.MK.m&:;&4Q##:A4v&>GO-q<0@NQ%&$A3e#N.&Jv#'=*eD?F7q#L?;)g%,(>7d#,1$1b#!>D6~$B/&#Z#!%/(l$'J?8l%81N!c#8J5Au$3*J.Q/'3N~$!9D!k@LA#m#2AH,}&#+J*|&A!*%o%215K^$=1!JU$=03'h##L5,u#8988n#GGAKZ$7#!:a%M(97Z%C;3*a&8!,(P%1)-Cy#4A+0x3037U#%'9A]$$>;$r##,DGm5I?-e%4<3+P#!2E,e#M$N8w#98&8x&*D,.p$BBEHa(%GBh%*$KKy#$=:Lr#3%Di#GI8>}#&L&8X%M#2;r%ACMFoIJJ$R##9GD{#+2.Ij%=!&3~%/&53Z&:I&3w%M5(NP#02;5f&*DJ=c$:KDF]&)7#Dg#*B,Ms;624p#3ECGw%#40(_#$<C2j%:)>>S#46DFQ$D(I=xJB=#l&!;)4VD5:7p$0NL#Y&G;I@T$((3<x%F6)Ml$+4@/WHEMBd%%6-AXJ6(5~,HL0~#:A.>k%K(:6f$<%,@s%.#+&^$I50?y&=&D(i$OK*/n$7?<Dc&82?KW#M$N-u#A+<1Q&23)>q$3):@]%'HEFR$:<L1q&1-I9U%,/'(p&#'ABY%&'-:~#2#)%Q&N/)y%71D5`&*=-#u%#7L<W%-GG?m$IF81y#3!-9t%L>-;a%-J5@[$8J3'uF&B:n&1M$E[&*E;V%7D4KVH2@NY%$64+w%:3J?Y$2+:!X&'.1>]&74K,~<96&y$8>5-f5FBg%?)N2~$LK8Db#N)!'p&3&HMg$F/F#a@/ABv3,1LxM>LGYH6$Jf%IO$(x%O&3M{8G;Bq$GI0?W'O$NZ%8H6w&@G0EV%6'MV#@!#=g&-<%-j'D2FUO3:5X%B4<0_#/&-#mKD3<e&.AM>r&##/!^&4D7,]#@7>OU&F2!:fNA=Lp#?M2Fp$B2G?Q#/'1/_#1==<v#F=;#h$)*8?o%G9'-o#1M0@P&&%'2l&2<C)]$$A;,s#!3+IX%,++Bd#'95MZ%3<K&m%L52Jg$4M#Oq&.4ADiF)LDU&+,*F]#>'M0o$LB,>U$>I0*Y$F13$R&>9@<w&@JL8W&%NL2R%+J/NfF12Bc/:4AZ%$@,:Y&/+G7VL:$Ob$/:H9S#0+8Bp$.AE-g&#N=NT>!AB`3(BH}$/'C+y#@*(Oj#!.L0{$$,L/n#<<D&z$432C}$LM(+j%?CN-u72$9j#:G;*}%8/.'d%..@0U&FB2+Z2*@?cF&!IW$4.!5z#JEBJa@/3&u$AOH&r83C)d%:EAKS%0LK/s$FGGOx%&I>8e#/6I7t&442:f5!J7x&9A5Of?BJNV#2$)Fl$+%)_%MJ9<z#HJ,8p$C@%(e##<<B|#NA2F}#:8-;g&/ED']&8D!,i$-4Ei9L<;}/:HEX#H$@Ot&EB>(r#,;GFe/9CMy$.*.(V$A%5AaA./M`%KE=L|$J/=3g%OOLNq%BO%@f%:7-?P$IJ$(t&=3,Le%81E#V%/70Jh53J7a&&&:Fd#G!FDwI,7'b#O,H%e&1C,6}&#?N9g$>/9;f%FG7+p&/CM'}&#@%Ax&=3AAY$+1K)f<$=Jr&E75-t%?736r%7#N.e#)L24`%6F-'{&,;=6[#H?B?w#2M*)d$LI<1~F>(Ir%'L,0o$CL.:x#13)Ad%&OK2o9MADV%E!./_%HB4(y/-@Dv7I#@`#-.L>r$IG@Aj%.;?K[%5)-#f&7,&0n#OL1j#<$?%~LM1$`%@/2Nc#5I!#}#KK.Jx'>B1u#8#H#}#(6CDS%C3D;c$A:!4QF#F/R%?3I6m%@<6B_/&!(m%$*1={E>ENZ%//20]&'%!Ec%J9?N^#C+>?d&'&,6}&D=M/T%N4:?X#:6:%c%18D@o&$)>.w%GF;A]7I-+{#D'E!p#&<E/i%4>'>`$DD'FQ$MC7Nb6(@3Q#*K,8s&A$;1R$L(?,x#*-8O]$1>?|%)2C1r%:C>Gw$'13Hy%A=JCj$F!BJx*&I2yJOF/n$3E*-S$)JFAn'#D!d&-)$KT;</:|N)85r%(?;3d$210Co$HNN.rL;,6u$1B:7|#<'>@y%88L/[<$L:~%B:'!|%M'H-o0IAF[#7)-@[&>O1I_#<;-+R#B8L9o#IH>Bj#8K)Ky&<&7_$42L,x5$,-v%%A+Ki#LA.(PH6-7XN1@8e&+/.;|H5&k#E3:;S&G-64T&7HC7b&3D&Fo&AA(.w#G<;Ls#.)N!~;'$Hw<,OA[#2L;Bx&@NHO{%';??|#(N&CR$6?D=V%!=)!Z$CD;BPM.I.X%317@w##=-,_%FH*<V9LD&^%+NOLX$L>3LZ&)70/y%I**Hk&7.C+[%@J8Mk$(O(#_#(G.0r%$!/'a#E$>*Z&;=$$w%)9%]%K#F:v%@*:3]%9A?C}%EO#E~%./.+e'FJ;|#<.3B{-#4Hl#,E7.o%3N+5wJ9)Cu&)O?IP%JO7Jb,MC;v%63J9]%7/F:X#O@OFQ%<A':u?52D_&8,$$y$L-B'Q%KDK/W#=(HN^4C?>k#.-B1Y%09>Kz&;0L7^#$:6I~%+31-b&/.:=a#EKO=hI:&<d:CDFc+G.~#+)-;W9:5=X#?=2#P#K&M1z$@E$!r$1)7X.MMDq%5D@6n&+'>:k#:3.Dl$-IH'x$DD$(t5$.8i%6*)J^$%0A%R,DF+eAG44r&=06@W#L$;C[#A8>>^1IMIu#2H/6e#+)(5e$-389f#,>-'Q)#@,X#OM4HXK5((k$:8A$^&AB*-Z%C%.`&GB-5U$?IC#u&6?B)|0?J$|&.J%A{&?KB4t&2OE7~4I3Jp#;K'%p%.AJ;U$88?HU&B@#)U#7D4H`&*.#)]=#':V5<:6g&B#<J~$GD3C~$4$.A`%-NN0vCOOIz#>HD+kFM+,gEE18j%/K5BX%1(L'Q&6G42h%FB!.Y$<NG=Y.:)@V%=?--{%'=2C^$4J/Ev&+A/>t$=K1Bb$!))2f?1FKy&H!C5{#H.;Hz&C?FDY#7.4;q$F0#BT&*$:3^&9??V%/&.*{$'?,&y#G4C8Y4;LHc&'065}#0#*&n%OL1Du$,@%;}$FC5Fd$44*=i218(P7JO4z&?.MHa$2C:-h&'/7(XO&%Eh#)JLOf$#LEHS%(5:2i%H'H$Z#$-=8c%06G;iOOJ;t#I@*.~C8)j$&H5Ms%F4;0]$7M''x%OA80p>F/$m$K>*>e$M;23]&,+5Mv&:;-;`%4#08XP";
ll fact_memo[100000];

template<class T>
int extend(const char arr[], T res[]){
  int i, j, s = 1, sz = 0;
  static int cnv[128], fg = 0;

  if(fg==0) REP(i,33,127) if(i!='"'&&i!='\\') cnv[i]=fg++;

  if(arr[0]<' ') return 0;
  res[0] = 0;

  for(i=0;;i++){
    if(arr[i]<' ') break;
    if(cnv[arr[i]] < 46){
      res[sz] = res[sz]*46 + cnv[arr[i]];
    } else {
      res[sz] = res[sz]*46 + (cnv[arr[i]]-46);
      if(s==-1) res[sz] *= -1, s = 1;
      res[++sz] = 0;
    }
  }
  return sz;
}

ll get_fact(int n){
  int i;
  ll f;
 
  f = fact_memo[n / 500000];
  i = n / 500000 * 500000;
  while(i<n){
    i++;
    f=f*i%MD;
  }
  return f;
}

int T;
ll C, P, CC;
char buf[200000];

int main(){
  int i, j, k;
  ll res;

  extend(fact_str, fact_memo);

  reader(&T);
  while(T--){
    C = P = CC = 0;
    
    k = reader(buf);
    rep(i,k){
      C = (C*10+buf[i]-'0') % MD;
      CC = CC*10+buf[i]-'0';
    }
    if(k>15) CC = 1000000000000000000LL;
    
    k = reader(buf);
    rep(i,k) P = P*10 + (buf[i]-'0');
    if(P >= MD || k >= 12){ writerLn(0); continue; }
    if(P > (CC+1)/2){ writerLn(0); continue; }
    
    C = (C+1-P+MD) % MD;
    if(C < P){ writerLn(0); continue; }
    
    res = get_fact(C) * get_inv(get_fact(C-P), MD) % MD;
    writerLn(res);
  }

  return 0;
}
0