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
Migrated from old NTUJ.
Regional Jakarta 2010
| No. | Testdata Range | Score |
|---|