#include using namespace std; #define REP(i,a,b) for(i=a;i'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 void reader(T *x, S *y){reader(x);reader(y);} template void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);} template 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 void writerLn(T x){writer(x,'\n');} template void writerLn(T x, S y){writer(x,' ');writer(y,'\n');} template void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');} template 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')MjDDz%,&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^#?$}#+;:)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&1o3%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%,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,?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>%$I1/Z&8Ex#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&&CP$8@)/p$)&;?w#*9K=`&?;1(z2#'hM'MNHMT&'>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.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$5Y$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-)_::6q$B7;$z#,=?.s&5;5?j#+$,$i&'=J't#0JN*X&@*4&P#C4x$4D04b&6,H>w&%I/2{%9I-K~$);'?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/j$M*?Co$1$:;}$>BC$t#0B.As$I,N3k@.$Oo&*3I/s#2#*8l&;:2Ne$J!-v%$85G^#BL&Ar$-<.2Z&0?:0P$1:$K0Bm%B%JGw.%5=i#J&&!^$N9G1W&!1J$_$#@4Lk$C+49T&A>:/h9!Z&A2J5T&G04*Z&'M!4]$MC?4t%J7CDt$*@:If$: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%.4NQ#!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~&(+C0kALC#}$/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;O~&$K)4u#0)EHw&8GG=Y%-CGNU#J+L@qODO5oK*@HQ$:/8*p%9D.(j&1G7$U#N%KO]%:-7Oz%7D,7P%G9~#LL51W1.G=r#/8>CX#9*6r#,--.PL.*8P#A#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>e76JU/3,'Q;8KEg#<#(.U&3+>%W3FO&`%G;G&V%7DMNh%0<7MX$%J.-q07'=~#LKC>]%6JC!Q#:A83T-F!5t#IME(z&'B@>V&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&_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-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>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#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%330S$,)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$/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%;/1)N^$G72>p,K>$X&C,&(_&>7)!Y#$9+/e&;L(.e&?G6*x$D!/KV$.HG,t,H;6t[+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%N6Jm%3E&FdG0=H_#AGO+-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%1EK3^)3.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/(7xL!!JS#'-K(Y&?M<-a&D$J2y07J=T)G*By&:7,4V%&G-&|#=@??P&;:O?V#?9DA~%9MA@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(_#$>S#46DFQ$D(I=xJB=#l&!;)4VD5:7p$0NL#Y&G;I@T$((3k%K(:6f$<%,@s%.#+&^$I50?y&=&D(i$OK*/n$7?q$3):@]%'HEFR$:-;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_#/&-#mKD3r&##/!^&4D7,]#@7>OU&F2!:fNA=Lp#?M2Fp$B2G?Q#/'1/_#1=='M0o$LB,>U$>I0*Y$F13$R&>9@!AB`3(BH}$/'C+y#@*(Oj#!.L0{$$,L/n#<8e#/6I7t&442:f5!J7x&9A5Of?BJNV#2$)Fl$+%)_%MJ9(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#&'>`$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;@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*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%k#.-B1Y%09>Kz&;0L7^#$:6I~%+31-b&/.:=a#EKO=hI:&: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#HD+kFM+,gEE18j%/K5BX%1(L'Q&6G42h%FB!.Y$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 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(i15) 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; }