思路：动态规划

按照题意来进行DP。

定义 $dp[i][j]$ 表示从第 $i$ 个数到第 $n$ 个数，进行加法和乘法的运算后，运算结果为 $j$ 的方案数。

假设第 $i$ 个数为 y，那么可以枚举第 $i+1$ 状态下结果为 $0$ 到 $9$ 的方案数。 用 $x$ 来表示。

那么状态转移就是 $dp[i + 1][x] => dp[i][(x \times y)\mod 10]$

题目内容

小红有一个特异数组，初始这些数组都是正整数。如果这个数组长度大于 $1$ ，就需要将最后两个数取出进行运算，并将运算结果再加到数组末尾。

运算有加法和乘法两种。不同于正常的运算，运算得到的结果只会有一位，就是正常运算结果的最低位（个位）。

例如，对于数组$[1,3,1,4]$，选择加法运算后，数组变为$[1,3,5]$，再接着选择第二种操作后，数组变为$[1,5]$。

现在，小红想问你，当特异数组只剩下一个数时，这个数为 $0,1,2,...,9$ 的可能有多少，换句话说，让你输出这 $10$ 个数为最终剩余的一个数的方案数，答案对 $10^9+7$ 取模。

输入描述

第一行，正整数$n$，代表特异数组的初始长度。

第二行，n个正整数$a_1，a_2，......，a_n$，代表初始的特异数组。

$1 \leq n \leq 200000$

$1 \leq a_i \leq 10^9$

输出描述

一行，$10$个整数，第$i$个数代表结果为$i$的方案数

样例

输入输出示例仅提供调试，后台判断数据一般不包含示例

输入

4
1 3 1 4

输出

0 0 1 1 0 1 1 1 2 1