UOJ Logo Universal Online Judge

UOJ

#692. 【UR #23】民意调查

附件下载 统计

跳蚤报社开展了一次民意调查!

新闻记者 djq 蚤在街头采访了 $n$ 只跳蚤,询问了他们是否期待这次迁都。采访结束之后,djq 蚤把第 $i$ 只跳蚤的期待程度完美地量化为一个正整数 $a_i$ ($1\leq a_i\leq V$)。

统计学中,一组统计数据的平均数和中位数之间没有一般的大小关系可言。根据数据的不同,可能小于,可能大于,当然也可能相等。

收集完期待程度的统计数据之后,djq 蚤开始思考:如果我当时只随机采访了这 $n$ 只跳蚤中的一部分跳蚤,那么平均数和中位数中谁更有可能更大呢?会是平均数小于中位数的情况更普遍吗?

djq 蚤找到了你,他想让你算算,这组数据的 $2^{n-1}$ 个大小为奇数的非空子集中,有多少个满足平均数小于中位数呢?

输出答案对 $998244353$ 取模后的结果。

输入格式

第一行两个整数 $n,V$。

第二行 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示期待程度。

输出格式

一行一个整数表示满足条件的非空子集个数对 $998244353$ 取模后的结果。

样例一

input

5 10
1 2 7 9 10

output

8

explanation

满足条件的子集分别为:

  1. $\{1,7,9\}$
  2. $\{1,7,10\}$
  3. $\{1,9,10\}$
  4. $\{2,7,9\}$
  5. $\{2,7,10\}$
  6. $\{2,9,10\}$
  7. $\{7,9,10\}$
  8. $\{1,2,7,9,10\}$

样例二

见附件下载。

数据范围与提示

子任务编号 $n\leq$ $V\leq$ 分值
$1$ $20$ $800$ $20$
$2$ $30$ $15$ $20$
$3$ $30$ $100$ $20$
$4$ $50$ $800$ $30$
$5$ $70$ $800$ $10$

对于所有数据 $1\leq n\leq 70, 1\leq a_i\leq V\leq 800$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{1GB}$