Add Them Up

You are given several single-digit numbers, each between 1 and 9. Using one or more of these digits, form every number you can, then add all of those numbers together.

Each digit may be used at most as many times as it is given. Numbers with the same value are counted only once.

For example, if you have two 2s, one 4, and one 6 as in the table above, the numbers you can form are 2, 4, 6, 22, 24, 26, 42, 46, 62, 64, 224, 226, 242, 246, 262, 264, 422, 426, 462, 622, 624, 642, 2246, 2264, 2426, 2462, 2624, 2642, 4226, 4262, 4622, 6224, 6242, 6422 — 34 in total, and their sum is 51622.

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

Each test case consists of $9$ integers $P_1, P_2, \dots, P_9$ ($0 \le P_i \le 9$), where $P_i$ is the number of available copies of the digit $i$.

For each test case, print on its own line the sum of all numbers you can form, taken modulo $10^9 + 7$.