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 \lt 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}$.

我们定义数字 $a$（其各位数字为 $a_1, \ldots ,a_k$）与数字 $b$（其各位数字为 $b_1, \ldots ,b_k$）的进位制和（radix sum）为一个数字 $s(a,b)$，其各位数字为 $(a_1+b_1)\bmod 10, \ldots ,(a_k+b_k)\bmod 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}$ 取模后输出。

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 \lt 100000$).

第一行包含一个整数 $n$ —— 数组的长度（$1 \leq n \leq 100000$）。

第二行包含 $n$ 个整数 $x_1, \ldots, x_n$ —— 数组元素（$0 \leq x_i \lt 100000$）。

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

输出 $n$ 个整数 $y_0, \ldots, y_{n-1}$ — 其中 $y_i$ 应等于对应方案数对 $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$.

在第一个例子中，存在以下序列：序列 $(5,5)$ 的基数和为 $0$，序列 $(5,6)$ 的基数和为 $1$，序列 $(6,5)$ 的基数和为 $1$，序列 $(6,6)$ 的基数和为 $2$。