<s> """<STR_LIT>""" <EOL> MOD = <NUM_LIT:10> ** <NUM_LIT:9> <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def __init__ ( self ) : <EOL> """<STR_LIT>""" <EOL> self . C = [ [ <NUM_LIT:1> for _ in xrange ( <NUM_LIT> ) ] for _ in xrange ( <NUM_LIT> ) ] <EOL> for n in xrange ( <NUM_LIT:1> , <NUM_LIT> ) : <EOL> for k in xrange ( <NUM_LIT:1> , n ) : <EOL> self . C [ n ] [ k ] = self . C [ n - <NUM_LIT:1> ] [ k - <NUM_LIT:1> ] + self . C [ n - <NUM_LIT:1> ] [ k ] <EOL> def solve ( self , cipher ) : <EOL> """<STR_LIT>""" <EOL> N , K = cipher <EOL> return self . C [ N + K - <NUM_LIT:1> ] [ K ] % MOD <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import sys <EOL> f = open ( "<STR_LIT>" , "<STR_LIT:r>" ) <EOL> testcases = int ( f . readline ( ) . strip ( ) ) <EOL> solution = Solution ( ) <EOL> for t in xrange ( testcases ) : <EOL> N = int ( f . readline ( ) . strip ( ) ) <EOL> K = int ( f . readline ( ) . strip ( ) ) <EOL> cipher = N , K <EOL> s = "<STR_LIT>" % ( solution . solve ( cipher ) ) <EOL> print s , </s>
