import std.bigint,std.conv,std.stdio,std.string;int M=10^^9+7,S=2700000;long z,a,e;void f(int n){z=0;foreach(c; ` !PKLF6<0";4P+Z#0(96K874.7LEK$F,FZWYYL]\Q3F4>[UTCF#BN7W F:XW\V@C@4[;SMT33'!HN?*\,);)FWPT)[I+>=_#F-G"I0NKK ZB!KT2:&4&^#AG;&D-_Z]0KRD:MU57:W:9>@K66Y.?9G" O:T/&4THU];>'=-=,MPUP'0JMJ'(Q#*K9G47XD[ L>A]+"TTF-?F9$L*$?+GE:?80S.)=^5/M%_ 9^WZ-:NP3HK@XAT4?94OCC)U&I1'"":Y_'J%+ /S;.SK+@IW_:,HN]D?);G-4P?*6?? W;2KRXJD74QK7:[;E-J%R.]LTY1P4J6POZ1>@/*]WIK,'/,XI;L+*K9?ET=2KV26DDX]FT2,>[NC50Q)/K?05X[Z0%D?YC+])>!YW^:',]W>O!P-0KL8H.=RX?S^(2ANZ:IJ&/A0VQ5C3710585B/@SFJ<,&R![)9;NSN;@M0'+8'86R1RVC-:CW!+FZS#;3LWWK.'I@IQ:*_@4=:F%NXF!N1_O5S^CI,9A-PZW38E?@]MS*.@-G;0ZK0 +-#RX1YXZ"VNUV=CMQF:<#[S!@XIMN(%_8&:=O3=%B!Y->6W!L+($A736C1Y!,3$PY57Y8N.B/B%H;+=W0TN/(#ZM&C#O/6=@$-Q4&)O&9[QJG@*+XX(N -A8%:[GN[:5->=&Z1ZYQ)Z-IE8E&1M9&#?,""/Z+M(=!^)Z7CF"UA=VT9LFHEO>'_JVSNKVS9/8W*_7I"JW"Z$ITW-\%_7R:Q5T"1;H.+H1V/QGF*S40;DE,3JIG)^P/)>&SX]B);G4= -*TNJ'$ELP5K?.,M=.Y4&5]:RBTD-@B.T>/ VKBP3]P5*6)GZSS.)/R7N*"OD.!TG+)!!U!]V@>&9EW2]&/8O_;\>J(%N+I"]$K8.J8F5JUVQGHIE!F(BB8DCSQUJF.3S5OG"BY!<:91/TZ#M?23+/B;L/?/,4O6JS7'>?_+*,*2TW=F'[- (KM P&PUV! 4UDPNN2K26'];WO>R(<)=;MH7*]9WLKNR@,\6GDV?"1F=G/>#\<': _@]Q8M!Z/^T8B8@HB?A]500AD CS,]7X)#.QZV^'W)-O% 58#QP;*K>YRV.(BO@VP;1N>5=W"V%:>*D35EO327F.P+KNIN"<&L5LQE=?/>7L #I(A6'2$/0T=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;}}