CF1103E.Radix sum

Let's define radix sum of number $a$ consisting of digits $a_1, \ldots ,a_k$ and number $b$ consisting of digits $b_1, \ldots ,b_k$ (we add leading zeroes to the shorter number to match longer length) as number $s(a,b)$ consisting of digits $(a_1+b_1)\mod 10, \ldots ,(a_k+b_k)\mod 10$ . The radix sum of several integers is defined as follows: $s(t_1, \ldots ,t_n)=s(t_1,s(t_2, \ldots ,t_n))$

You are given an array $x_1, \ldots ,x_n$ . The task is to compute for each integer $i (0 \le i < n)$ number of ways to consequently choose one of the integers from the array $n$ times, so that the radix sum of these integers is equal to $i$ . Calculate these values modulo $2^{58}$ .

The first line contains integer $n$ — the length of the array( $1 \leq n \leq 100000$ ).

The second line contains $n$ integers $x_1, \ldots x_n$ — array elements( $0 \leq x_i < 100000$ ).

Output $n$ integers $y_0, \ldots, y_{n-1}$ — $y_i$ should be equal to corresponding number of ways modulo $2^{58}$ .

In the first example there exist sequences: sequence $(5,5)$ with radix sum $0$ , sequence $(5,6)$ with radix sum $1$ , sequence $(6,5)$ with radix sum $1$ , sequence $(6,6)$ with radix sum $2$ .