Опрелим цифровую сумму числа \(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\) целых чисел \(y_0, \ldots, y_{n-1}\) — \(y_i\) должно равняться остатку при делении соответствующего количества способов на \(2^{58}\).
Примечание
В первом примере существуют последовательности: последовательность \((5,5)\) с цифровой суммой \(0\), последовательность \((5,6)\) с цифровой суммой \(1\), последовательность \((6,5)\) с цифровой суммой \(1\), последовательность \((6,6)\) с цифровой суммой \(2\).