对于由正整数构成的可重集合 $A$，将其所有元素按照任意顺序排列得到序列 $a=a_1,a_2,\cdots,a_n$。记长为 $n+1$ 的序列 $b=b_0,b_1,\cdots,b_n$ 满足 $\displaystyle b_i=\lfloor\frac{\sum_{j=1}^ia_j}{10}\rfloor$。记 $\displaystyle f(A)=\max_{a}{\|\{b\}\|}$，其中 $\|S\|$ 表示不可重集合 $S$ 的大小。即任选 $a$，求 $b$ 中不同数的个数的最大值。特别地，有 $f(\emptyset)=1$。

给定可重集合 $A$，对其 $A$ 的所有本质不同的子集 $B$ 求 $f(B)$ 之和 $\bmod998244353$ 的值。

称两个可重集合 $X,Y$ 是本质不同的，当且仅当存在一个数 $v$，$v$ 在 $X,Y$ 中的出现次数不同。

输入格式

第一行一个整数 $n$ 表示集合 $A$ 的大小，接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，可重集合 $S$ 即为 $\{a_1,a_2,\cdots,a_n\}$。

输出格式

一行，表示答案对 $998244353$ 取模后的值。

样例一

input

1
1

output

2

样例二

input

6
1 1 2 2 3 3

output

31

样例三

input

12
1 2 3 4 5 6 7 8 9 10 11 12

output

18228

数据范围与约束

对于所有数据，$n\le 2000, 1\le a_i\le 12$。