Положительная сумма замыкания
Положительное замыкание или замыкание Клини можно описать как множество строк конечной длины, которые могут быть созданы путем конкатенации произвольных элементов из множества строк, при этом разрешается использовать один и тот же элемент несколько раз. В случае чисел это означает возможные числа, которые могут быть сгенерированы. Учитывая количество доступных четных цифр от 1 до 10, найдите сумму всех положительных замыканий из этих цифр.
Например,
Предположим, что у нас есть возможность использовать до двух цифр 2 и одну цифру 4. Существует ровно 8 различных чисел, которые можно построить с использованием указанных цифр: 2, 4, 22, 24, 42, 224, 242, 422. Сумма всех этих чисел равна 982.
Входные данные
Первая строка ввода содержит целое число T (T ≤ 500), обозначающее количество тестовых случаев. Каждый тестовый случай содержит девять целых чисел P_i (0 ≤ P_i ≤ 9), обозначающих количество i-й цифры для i = 1..9.
Выходные данные
Для каждого тестового случая выведите строку в формате Case #x: M, где x — номер случая (начиная с 1), а M — сумма всех возможных чисел, сгенерированных из доступных цифр. Выведите результат по модулю 1000000007.