Positive Closure Sum
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 1 to 10, sum all positive closures from those digits.
For example,
It means that we can use up to two digits of 2 and one digit of 4. There are exactly 8 distinct numbers that can be constructed using the above digits: 2, 4, 22, 24, 42, 224, 242, 422. The sum of all those numbers is 982.
Input
The first line of input contains an integer T (T ≤ 500) denoting the number of testcases. Each testcase contains nine (not four) integers P_i (0 ≤ P_i ≤ 9) denoting the number of i-th digit for i = 1..9.
Output
For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the output in a single line the sum of all possible numbers generated from the available digits. Modulo the output with 1000000007.