Sum of all numbers made from even digits

The positive closure of a set of strings is the set of all finite, non-empty strings obtained by concatenating members of that set, where the same member may be used more than once. Here the members are single digits, so every element of the closure is a number.

Only the four even digits 2, 4, 6, 8 are usable, and for each of them the input gives how many copies are available. Build every number that can be written without exceeding those counts, count each distinct number once, and add them all up. The sum can grow large, so print it modulo 1,000,000,007.

Suppose two copies of 2 and one copy of 4 are available. Exactly eight distinct numbers can be written: 2, 4, 22, 24, 42, 224, 242, 422, and their sum is 982. The number 2 counts once even though two copies of the digit 2 are available.

If no even digit is available, no number can be written and the sum is 0.

The first line contains an integer $T$ ($1 \le T \le 500$), the number of test cases.

Each of the next $T$ lines contains nine integers $P_1, P_2, \dots, P_9$ ($0 \le P_i \le 9$), where $P_i$ is the number of copies of the digit $i$ that are available. The odd entries $P_1, P_3, P_5, P_7, P_9$ are part of the input but are never used, because a number may contain even digits only.

For each test case, print one line in the form Case #x: M, where $x$ is the test case number starting from 1 and $M$ is the sum of all numbers that can be written, modulo 1,000,000,007.