import std.bigint,std.conv,std.stdio,std.string;int M=10^^9+7,S=2500000;long z,a,e;void f(int n){z=0;foreach(c; ` !')D,.Z#Q;X2*,1EHKAMQ(9F=#CL36BU-9B6=19Q\V;LPBB\P!.?9"QR$COW,T6PH0;I;_?;YN2XK)(_ -/B9U*32,+D\^NQ$ Z6-K4%O@834^7 -_WC!H9MS=M9>.D([Z$D-_Z]E20SLC_F>OCC)U9,AA>YT=]KLFPX -U^>PX_>8!/E&?OM>%Y)G2O=R!6##W=F(\U#]3^J5P!KDNR^$#($Y*C@I+>H&R@\R[7Z QG^^W$&C #CLU928"#P5 2H.O-WH#+%CA9YQV4M:#38W.$K,>L/*):$T&VHJ_<'V[\5_5S\#$T>^;KPR.4@=9E0!B>^K%2P:W[-F.M.LFD(&YF!+"5_$AJ8B[F&T O&LO,! '!5E)]^,1D%!WP($XD\&XYO)U U.<*T*'(,]W>OI4U0%[7S^QM9$2T8_OK.,6"=)D.3R["5V"D=V4X$5_*-.FSK5FE="LFGTL&%7L!HKAE4LV=_;JR'J) M;L>8>3 M(8#CT$"!V*QT5*+IQ%F6EKZ1"9M?'=B]RPUDZA8!W9VC-:C2:]PWO(5O^E.DN(G98PW7 E $U4VQ]JO%I*7NS9U+1X]4IF*#)*LSI>SPSA+(VEWIRD=IIMJM&2),AI[0 0(111DS="AFU2]5?KM<=;%^&F/*R$H"O\#I$%U,3W=<$F*SC-JA2WGZOD2>H=%$'VJ_0+)US00*BCE/,Y]EK+G-['\8@(>;^FFDE,3J00M*SY^(ORAH-:X/QA->3<,O-S3GCH"H73*- U,Q-(TB%?[7"3L>,]+L_T*%Y+H:MXB6WAE[^182CMX;:%2$61N8F,[+"W(P]$-?M6D[D(H1/1HP] GN>*C9IHRLQ.A<%N9)*K\?Y&/VJF'-3'MG$2;J>./W9^QQ*'T+A_, #%>G9U7LRS2"C2"/V+< HD0EZ8"NGB479:'W238L+_JI,$E?67I;LHW](:,FPKJ2BO!+,^$KUM3)G*H4OAT?,S/$E,[]Z*W3CU:,.3'*RKP/H"=S!W$L-YF8V\&E[5%AE.1\CG_\Z+JHA.,R@NF LG5RU(%?+9PW2ZXY5 > ,''9:Q835)41'+O:>%D<91/TZP)G;N3R(O&Y66%#EB<91;\(2D45'A'D P47H&N*!7*)S(HT' ,%$V6]PBC$!2SWRP#G1!Z;S9R*Q&N)XJRK+(*> DKNIVI)&]#2-J8'F\)Q5D;&9$,V/27B! B(7;7=3+O@]Q8ME:4. 5(YVAH]M;J-?\B*.IHL6FRU(G"*<;$T%/^BB]'.Y&]*VUXUTXD!. K4*0D%Z["];(/AFD%F3^U]+C-_=0&&l/M==r/M){f(r%M);a=z;f(l%M);for(e=M-2;e;e/=2,z=z*z%M)if(e&1)a=a*z%M;}a.writeln;}}