Given the number of available digit of \textbf{1} to \textbf{9}, sum all possible numbers generated from those digits. For example, It means that we can use up to two digits of \textbf{2}, one digit of \textbf{4} and one digit of \textbf{6}. There are exactly \textbf{34} distinct numbers that can be constructed using the above digits: \textbf{2}, \textbf{4}, \textbf{6}, \textbf{22}, \textbf{24}, \textbf{26}, \textbf{42}, \textbf{46}, \textbf{62}, \textbf{64}, \textbf{224}, \textbf{226}, \textbf{242}, \textbf{246}, \textbf{262}, \textbf{264}, \textbf{422}, \textbf{426}, \textbf{462}, \textbf{622}, \textbf{624}, \textbf{642}, \textbf{2246}, \textbf{2264}, \textbf{2426}, \textbf{2462}, \textbf{2624}, \textbf{2642}, \textbf{4226}, \textbf{4262}, \textbf{4622}, \textbf{6224}, \textbf{6242}, \textbf{6422}. The sum of all those numbers is \textbf{51622}. \InputFile The first line contains the number of test cases \textbf{t} (\textbf{t} ≤ \textbf{500}). Each testcase contains nine integers \textbf{P_i} (\textbf{0} ≤ \textbf{P_i} ≤ \textbf{9}) denoting the number of \textbf{i}-th digit (\textbf{1} ≤ \textbf{i} ≤ \textbf{9}). \OutputFile For each testcase, output in a single line the sum of all possible numbers generated from the available digits. Print the answer modulo \textbf{1,000,000,007}.