Just Sum It#3331

Just Sum It

3 seconds
64 megabytes
Easy

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 .

Input

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).

Output

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.

Examples

Example 1

Loading
Loading