对于由正整数构成的可重集合 $ 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 $。