Given the number of available digits from to , sum all possible numbers generated from those digits. For example,
Digit can be used twice when forming a number, while digits and can be used once each. There are exactly distinct numbers that can be constructed using the above digits: , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . The sum of all those numbers is .
The first line contains the number of test cases (t \leq 500). Each testcase contains nine integers p_i (0 \leq p_i \leq 9) denoting the number of -th digit (1 \leq i \leq 9).
For each testcase, output in a single line the sum of all possible numbers generated from the available digits. Print the answer modulo 1{,}000{,}000{,}007.
Example 1