Вам задана деяка кількість цифр від до . Просумуйте усі числа, які можна утворити з них. Наприклад,
Цифра при утворенні числа може використовуватися двічі, по одному разу дозволено використовувати цифри та . Із вказаних цифр можна утворити в точності різні числа: , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . Їх сума дорівнює .
Перший рядок містить кількість тестів (t \leq 500). Кожний тест містить дев'ять цілих чисел p_i (0 \leq p_i \leq 9), що вказують на кількість цифр (1 \leq i \leq 9), що є в наявності.
Для кожного тесту вивести в окремому рядку суму усіх чисел, які можна згенерувати використовуючи задані цифри. Відповідь слід вивести за модулем 1\,000\,000\,007.
Приклад 1