시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 5 5 35.714%

문제

Given the number of available digit of 1 to 9, sum all possible numbers generated from those digits.

For example,

Digit 1 2 3 4 5 6 7 8 9
Frequency 0 2 0 1 0 1 0 0 0

It means that we can use up to two digits of 2, one digit of 4 and one digit of 6. There are exactly 32 distinct numbers that can be constructed using the above digits: 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. The sum of all those numbers is 51622.

입력

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

출력

For each testcase, output in a single line the sum of all possible numbers generated from the available digits. Modulo the output with 1,000,000,007.

예제 입력

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

예제 출력

96
51622
454976431

힌트