Вам задано некоторое количество цифр от \textbf{1} до \textbf{9}. Просуммируйте все числа, которые можно образовать из них. Например Цифра \textbf{2} при образовании числа может использоваться дважды, по одному разу разрешено использовать цифры \textbf{4} и \textbf{6}. Из указанных цифр можно образовать в точности \textbf{34} различных числа: \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}. Их сумма равна \textbf{51622}. \InputFile Первая строка содержит количество тестов \textbf{t} (\textbf{t} ≤ \textbf{500}). Каждый тест содержит девять целых чисел \textbf{p_i} (\textbf{0} ≤ \textbf{p_i} ≤ \textbf{9}) указывающих на количество имеющихся в наличии цифр \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{9}). \OutputFile Для каждого теста вывести в отдельной строке сумму всех чисел, которые можно сгенерировать, используя имеющиеся цифры. Ответ следует вывести по модулю \textbf{1,000,000,007}.