Positive Closure or Kleene Closure can be described as the set of finite-length strings that can be generated by concatenating arbitrary elements of set of strings allowing the use of the same element multiple times. In case of numbers, in short, it is a possible numbers generated. Given the number of available even digit of \textbf{1} to \textbf{10}, sum all positive closures from those digits. For example, It means that we can use up to two digits of \textbf{2} and one digit of \textbf{4}. There are exactly \textbf{8} distinct numbers that can be constructed using the above digits: \textbf{2}, \textbf{4}, \textbf{22}, \textbf{24}, \textbf{42}, \textbf{224}, \textbf{242}, \textbf{422}. The sum of all those numbers is \textbf{982}. \InputFile The first line of input contains an integer \textbf{T} (\textbf{T} ≤ \textbf{500}) denoting the number of testcases. Each testcase contains nine (not four) integers \textbf{P_i} (\textbf{0} ≤ \textbf{P_i} ≤ \textbf{9}) denoting the number of \textbf{i}-th digit for \textbf{i = 1..9}. \OutputFile For each test case, the output contains a line in the format \textbf{Case #x: M}, where \textbf{x} is the case number (starting from \textbf{1}) and \textbf{M} is the output in a single line the sum of all possible numbers generated from the available digits. Modulo the output with \textbf{1000000007}.