对于由正整数构成的可重集合 A,将其所有元素按照任意顺序排列得到序列 a=a1,a2,⋯,an。记长为 n+1 的序列 b=b0,b1,⋯,bn 满足 bi=⌊∑ij=1aj10⌋。记 f(A)=max,其中 |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 。
子任务编号 | n\le | 特殊性质 | 子任务分值 |
---|---|---|---|
1 | 20 | 无 | 4 |
2 | 40 | 无 | 12 |
3 | 2000 | a_i\le 11 | 16 |
4 | 2000 | a_i\ne1 | 12 |
5 | 100 | 无 | 12 |
6 | 300 | 无 | 8 |
7 | 600 | 无 | 12 |
8 | 2000 | 无 | 24 |