Radix sum

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，对于每一个 $p \in [0,n-1]$，求满足下列条件的整数序列 $i_1,i_2,...,i_n$ 的方案数，对 $2^{58}$ 取模： - $\forall j \in [1,n] , i_j \in [1,n]$； - $\sum\limits_{j=1}^n a_{i_j} = p$，这里的加法定义为十进制不进位加法。

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

2
5 6

1
2

4
5 7 5 7

16
0
64
0

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 $ .