import std.bigint,std.stdio,std.string;int M=10^^9+7,S=4672898,j;long y,z,e;void i(long x){y=1;for(e=M-2;e;e/=2,x=x*x%M)if(e&1)y=y*x%M;}void f(int n){if(n>M/2){f(M-1-n);z.i;z=n%2?y:M-y;}else{j=n%S;if(j>S-j){for(z=1,j=S-j;j--;)z=z*++n%M;z.i;}else{for(y=1;j--;)y=y*n--%M;}for(z=0,j=5;j--;)z=z<<6|`! G2UN=_Q>!)K9A9Z>\?J.>9G%[N.">K*3Q*XY-[* OPH&0=:'0:4\T8#F@'EDPUH.H/*/42BL5ZD_#=#:M6L%5+A$*XCCV.@CG%"PL/RWN9$KLA6U_.WKYT/!94VR#:$*%ID'7-_L1KN,12^X'U52SW-K#ZZ4W?RUZ,RWOK:H2M00S%;.=]\#P+MIH+XG!R:"A>0R#A:$5N3P^A@\_D5R%Y"GFPIZ[Y'V[S%&(F\DI.U-X:2=Z((@D3E3!"_F:"5Z=*TT"@L/?F8V7DU0C'*^UTKV_7'P^&I'?F[C$F@[9G\LEBHT0Z%"?E7L3N_["UL*#N%RCU1T"?]<>YE5$J<]>M;]>,"JA[8RO!EZ1U,I"4IFKZ<.%&GBS*II_MG@WTH"(VDH#,ZADSU=NE":O&9G.