Вам задана деяка кількість цифр від \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}.