import std.bigint,std.stdio,std.string;int M=10^^9+7,S=4672898,j;long y,z,e;void i(long x){for(y=1,e=M-2;e;e/=2,x=x*x%M)y=e%2?y*x%M:y;}void f(int n){if(n>M-n){f(M-1-n);z.i;z=n%2?y:M-y;}else{if(n%S>S/2){for(z=1;n%S;)z=z*++n%M;z.i;}else{for(y=1;n%S;)y=y*n--%M;}for(z=j=0;j<5;)z=z<<6|` !=NU2G)!>Q_Z9A9K.J?\>[%G9>K>".NX*Q3* *[-Y0&HPO:0':=#8T\4T<'@FUPDE>*/H.HLB24/#_DZ56M:#=A+5%LCCX*$GC@.V.S?$9NWRU6ALKYKW._49!/T$:#RV'DI%*1L_-721,NK5U'X^K-WS2W4ZZ#,ZUR?:KOWR00M2H=.;%S+P#\]X+HIM":R!G#R0>AN5$:A@A^P3R5D_\FG"Y%Y[ZIP%S[V'D\F(&X-U.I(Z=2:E3D@(F_"!3=Z5":@"TT*8F?/L0UD7VU^*'C7_VKTI&^P'C[F?'9[@F$BEL\G%Z0THL7E?""[_N3N#*LU1UCR%<]?"T$5EY>M>]];R8[AJ1ZE!OOU.