题目背景

你能走到这里很了不起......

题目描述

白给了你一个长度为 $n$ 的整数序列 $a_1,\ldots, a_n$ 和一个整数 $m$，她请你求出以下式子的值：

$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=0}^m \min(a_i \oplus k, a_j \oplus k) $$

其中，$\oplus$ 表示二进制下按位异或。

由于答案可能很大，所以你仅需要输出答案对 $998244353$ 取模后的值。

输入格式

第一行，两个非负整数 $n, m$。

第二行，$n$ 个非负整数 $a_1, \ldots, a_n$。

输出格式

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

2 3
1 5

40

5 7
1 2 3 4 5

460

10 197
1 5 102 289 445 326 117 64 100 266

2788560

10 0
3701780 6015893 9822195 8016360 992671 8828219 5674666 4815987 1784800 995151

333221210

8 33554432
2117455 10849252 28912108 3049487 10134324 20812345 26061978 24220183

42695030

8 51937970
93102591 5826965 25429632 51808294 13143740 21293750 85706705 22127009

345700571

13 189320127
90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115

425145733

10 1000000000
530093637 530093637 530093637 540208320 451233002 540208320 540208320 895132935 619514612 895132935

644847220

提示

【样例解释 #1】

当 $i = j = 1$ 时，$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = (1 \oplus 0) + (1 \oplus 1) + (1 \oplus 2) + (1 \oplus 3) = 1 + 0 + 3 + 2 = 6$；

当 $i = j = 2$ 时，$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = (5 \oplus 0) + (5 \oplus 1) + (5 \oplus 2) + (5 \oplus 3) = 5 + 4 + 7 + 6 = 22$；

当 $i = 1, j = 2$ 或 $i = 2, j = 1$ 时，$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = \min(1, 5) + \min(0, 4) + \min(3, 7) + \min(2, 6) = 6$。

因此，答案为 $6 + 22 + 6 \times 2 = 40$。

【数据范围】

本题采用捆绑测试。

子任务编号	$n\le$	$m\le$	$a_i\le$	特殊性质	分值
1	$100$				$1$
2	$2\times 10^5$	$0$	$10^9$		$8$
3	$3000$	$10^6$	$10^6$		$21$
4	$2\times 10^5$		$10^9$		$16$
5		$10^9$		A	$9$
6				B	$24$
7					$21$

• 特殊性质 A：保证 $a_1 = a_2 = \cdots = a_n$。
• 特殊性质 B：保证存在非负整数 $k$ 使得 $m = 2^k - 1$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 2\times 10^5$，$0 \leq m \leq 10^9$，$0 \leq a_i \leq 10^9$。