让我们定义由数字 $$$a_1、\ldots 、a_k$$$ 组成的数字 $$$a$$$ 和由数字 $$$b_1、\ldots 、b_k$$$ 组成的数字 $$$b$$$ 的基数和(我们在较短的数字上添加前导零以匹配较长的长度)为由数字组成的数字 $$$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}$$$。
示例
输入 #1
2 5 6
输出 #1
1 2
输入 #2
4 5 7 5 7
输出 #2
16 0 64 0
注意
在第一个示例中,存在序列:序列$$$(5,5)$$$,基数和$$$0$$$,序列$$$(5,6)$$$,基数和$$$1$$$,序列$$$(6,5)$$$,基数和$$$1$$$,序列$$$(6,6)$$$,基数和$$$2$$$。