E. Цифровая сумма
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Опрелим цифровую сумму числа $$$a$$$, состоящего из цифр $$$a_1, \ldots ,a_k$$$ и числа $$$b$$$, состоящего из цифр $$$b_1, \ldots ,b_k$$$(мы добавляем к меньшему по длине числу ведущие нули, чтобы уравнять длину чисел) как число $$$s(a,b)$$$, состоящее из цифр $$$(a_1+b_1)\mod 10, \ldots ,(a_k+b_k)\mod 10$$$. Цифровая сумма нескольких чисел определяется следующим образом: $$$s(t_1, \ldots ,t_n)=s(t_1,s(t_2, \ldots ,t_n))$$$

Вам дан массив $$$x_1, \ldots ,x_n$$$. Задача состоит в том, чтобы посчитать для каждого числа $$$i (0 \le i < n)$$$ количество способов последовательно выбрать одно число из массива $$$n$$$ раз, чтобы цифровая сумма этих чисел была равна $$$i$$$. Вычислите эти значения по модулю $$$2^{58}$$$.

Входные данные

В первой строке записано одно целое число $$$n$$$ — длина массива($$$1 \leq n \leq 100000$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$x_1, \ldots x_n$$$ — элементы массива($$$0 \leq x_i < 100000$$$).

Выходные данные

Выведите $$$n$$$ целых чисел $$$y_0, \ldots, y_{n-1}$$$ — $$$y_i$$$ должно равняться остатку при делении соответствующего количества способов на $$$2^{58}$$$.

Примеры
Входные данные
2
5 6
Выходные данные
1
2
Входные данные
4
5 7 5 7
Выходные данные
16
0
64
0
Примечание

В первом примере существуют последовательности: последовательность $$$(5,5)$$$ с цифровой суммой $$$0$$$, последовательность $$$(5,6)$$$ с цифровой суммой $$$1$$$, последовательность $$$(6,5)$$$ с цифровой суммой $$$1$$$, последовательность $$$(6,6)$$$ с цифровой суммой $$$2$$$.