You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

脑袋空空

题目背景

旧地狱的地狱鸦，灵乌路空，即使取得了神明的力量，也依然脑袋空空，与雾之湖的笨蛋是同一类呢。

为了考验琪露诺，阿空脑袋里想了一个很长很长的大数字。可是毕竟是鸟脑袋，阿空将大数字里所有的数字都搞乱了，只记得里面有哪些数字。

可怜的阿空只能试图对每一种可能的数字排列进行计算，你能帮帮她吗？

题目描述

已知一个长度为 $n$ 的序列 $a=[a_1,a_2,\cdots,a_n]$，其中 $a_i$ 的值在 $0\sim 9$ 内。

我们可以将序列 $a$ 重新排列。具体而言，找到一个 $1,2,\cdots ,n$ 均出现且仅出现过一次的序列 $p=[p_1,p_2,\cdots,p_n]$，生成 $a$ 的一个重排 $b=[a_{p_1},a_{p_2},\cdots,a_{p_n}]$。对于每个 $b$，我们可以将其拼接成一个十进制大整数。这个重排方案的分数就是这个大整数。

例如，$a=[1,1,3]$，那么有以下重排方式：

• $p=[1,2,3]$，得到 $b=[1,1,3]$，分数为 $113$；
• $p=[1,3,2]$，得到 $b=[1,3,1]$，分数为 $131$；
• $p=[2,1,3]$，得到 $b=[1,1,3]$，分数为 $113$；
• $p=[2,3,1]$，得到 $b=[1,3,1]$，分数为 $131$；
• $p=[3,1,2]$，得到 $b=[3,1,1]$，分数为 $311$；
• $p=[3,2,1]$，得到 $b=[3,1,1]$，分数为 $311$。

将所有重排方案的分数相加，得到的数记为 $a$ 的分数。对于上面那个例子，$a$ 的分数为 $S=113+131+113+131+311+311=1110$。

注意：由 $b$ 序列组成的大整数允许有前导零（即 $0$ 作为该数的第一个数字，如 $010,0000,0123$）。

由于 $a$ 序列的分数可能很大，你只需要求出 $a$ 序列的分数对 $998{,}244{,}353$ 取模后的结果即可。

输入格式

第一行有一个整数 $n$，表示序列 $a$ 的长度。

第二行有 $n$ 个整数 $a_1,a_2,\cdots,a_n$，描述序列 $a$。

输出格式

输出共一行一个整数，表示 $a$ 的分数对 $998{,}244{,}353$ 取模后的结果。

样例 #1

样例输入 #1

3
1 1 3

样例输出 #1

1110

样例 #2

样例输入 #2

10
0 1 2 3 4 5 6 7 8 9

样例输出 #2

480049370

提示

数据范围及约定

• 对于 $20\%$ 的数据，满足 $n\le 4$；
• 对于 $50\%$ 的数据，满足 $n\le 10$；
• 另有 $20\%$ 的数据，满足 $a_i=1$；
• 对于全部数据，满足 $1\le n\le 10^6$，$a_i\in\{0,1,2,3,4,5,6,7,8,9\}$。