<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> MOD = <NUM_LIT> <EOL> class Solution ( object ) : <EOL> def __init__ ( self ) : <EOL> self . lens = [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> ] <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , M = cipher <EOL> f = [ <NUM_LIT:0> for _ in xrange ( M + <NUM_LIT:1> ) ] <EOL> s = [ <NUM_LIT:0> for _ in xrange ( M + <NUM_LIT:1> ) ] <EOL> f [ <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> for l in self . lens : <EOL> if j - l >= <NUM_LIT:0> : <EOL> f [ j ] += f [ j - l ] <EOL> f [ j ] %= MOD <EOL> f_N = map ( lambda x : pow ( x , N , MOD ) , f ) <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> s [ j ] = f_N [ j ] <EOL> if s [ j ] <= <NUM_LIT:0> : break <EOL> for k in xrange ( <NUM_LIT:1> , j ) : <EOL> s [ j ] -= f_N [ j - k ] * s [ k ] <EOL> s [ j ] %= MOD <EOL> return s [ M ] <EOL> class Solution_TLE ( object ) : <EOL> def __init__ ( self ) : <EOL> self . lens = [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> ] <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , M = cipher <EOL> f = [ [ <NUM_LIT:0> for _ in xrange ( M + <NUM_LIT:1> ) ] for _ in xrange ( N + <NUM_LIT:1> ) ] <EOL> s = [ [ <NUM_LIT:0> for _ in xrange ( M + <NUM_LIT:1> ) ] for _ in xrange ( N + <NUM_LIT:1> ) ] <EOL> f [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] = <NUM_LIT:1> <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> for l in self . lens : <EOL> if j - l >= <NUM_LIT:0> : <EOL> f [ <NUM_LIT:1> ] [ j ] += f [ <NUM_LIT:1> ] [ j - l ] <EOL> f [ <NUM_LIT:1> ] [ j ] %= MOD <EOL> for i in xrange ( <NUM_LIT:2> , N + <NUM_LIT:1> ) : <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> f [ i ] [ j ] = f [ i - <NUM_LIT:1> ] [ j ] * f [ <NUM_LIT:1> ] [ j ] <EOL> f [ i ] [ j ] %= MOD <EOL> for i in xrange ( <NUM_LIT:1> , N + <NUM_LIT:1> ) : <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> s [ i ] [ j ] = f [ i ] [ j ] <EOL> if s [ i ] [ j ] <= <NUM_LIT:0> : break <EOL> for k in xrange ( <NUM_LIT:1> , j ) : <EOL> s [ i ] [ j ] -= f [ i ] [ j - k ] * s [ i ] [ k ] <EOL> s [ i ] [ j ] %= MOD <EOL> return s [ N ] [ M ] <EOL> def solve_error ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , M = cipher <EOL> f = [ [ <NUM_LIT:0> for _ in xrange ( M + <NUM_LIT:1> ) ] for _ in xrange ( N + <NUM_LIT:1> ) ] <EOL> f [ <NUM_LIT:1> ] [ <NUM_LIT:1> ] = <NUM_LIT:1> <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> for l in self . lens : <EOL> if j - l >= <NUM_LIT:1> : <EOL> f [ <NUM_LIT:1> ] [ j ] += f [ <NUM_LIT:1> ] [ j - l ] <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> f [ <NUM_LIT:1> ] [ j ] -= f [ <NUM_LIT:1> ] [ j - <NUM_LIT:1> ] <EOL> for i in xrange ( <NUM_LIT:2> , N + <NUM_LIT:1> ) : <EOL> for j in xrange ( <NUM_LIT:1> , M + <NUM_LIT:1> ) : <EOL> cmb = i <EOL> for l in xrange ( <NUM_LIT:1> , i + <NUM_LIT:1> ) : <EOL> f [ i ] [ j ] += cmb * f [ i - l ] [ j - <NUM_LIT:1> ] * ( f [ <NUM_LIT:1> ] [ j ] ** i ) <EOL> cmb = cmb * ( i - l ) / ( l + <NUM_LIT:1> ) <EOL> return f [ N ] [ M ] <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> solution = Solution ( ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> for t in xrange ( testcases ) : <EOL> cipher = map ( int , f . readline ( ) . strip ( ) . split ( '<STR_LIT:U+0020>' ) ) <EOL> s = "<STR_LIT>" % ( solution . solve ( cipher ) ) <EOL> print s , </s>
