시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB833100.000%

문제

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,

Even Digit 2 4 6 8
Frequency 2 1 0 0

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.

입력

The first line of input contains an integer T (T ≤ 500) denoting the number of testcases. Each testcase contains nine (not four) integers Pi (0 ≤ Pi ≤ 9) denoting the number of i-th digit for i = 1..9.

출력

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 1,000,000,007.

예제 입력 1

3
0 2 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0

예제 출력 1

Case #1: 982
Case #2: 2
Case #3: 147320